#include <algorithm> #include <map> #include <set> #include <stdio.h> #include <vector> using Lines = std::vector<int>; using Range = std::pair<int, int>; using Ranges = std::vector<Range>; using Positions = std::multimap<int, int>; using LinesKey = std::tuple<int, int, int>; int getMaxDistance(const Ranges& ranges, const Positions& startPositions, const Positions& stopPositions) { std::map<LinesKey, int> linesSum; std::set<int> currentLines; for (const Range& range : ranges) { const auto rangeStart = startPositions.equal_range(range.first); for (auto it = rangeStart.first; it != rangeStart.second; ++it) { currentLines.insert(it->second); } const auto rangeStop = stopPositions.equal_range(range.first); for (auto it = rangeStop.first; it != rangeStop.second; ++it) { currentLines.erase(it->second); } if (currentLines.empty()) { const LinesKey key = std::make_tuple(0, 0, 0); linesSum[key] += range.second - range.first; } else { const LinesKey key = std::make_tuple(*currentLines.begin(), *currentLines.rbegin(), currentLines.size()); linesSum[key] += range.second - range.first; } } int max = 0; for (const auto& it : linesSum) { max = std::max(max, it.second); } return max; } void preparePositions(Ranges& ranges, Positions& positionsStart, Positions& positionsStop) { std::sort(ranges.begin(), ranges.end()); for (unsigned int i = 0; i < ranges.size(); ++i) { positionsStart.insert({ ranges[i].first, i }); positionsStop.insert({ ranges[i].second, i }); } } Ranges prepareLines(Lines& lines) { std::sort(lines.begin(), lines.end()); lines.erase(std::unique(lines.begin(), lines.end()), lines.end()); Ranges ranges; for (unsigned int i = 0; i < lines.size() - 1; ++i) { ranges.push_back({ lines[i], lines[i + 1] }); } return ranges; } void readData(int& x, int& y, Ranges& xRangesLines, Ranges& yRangesLines) { int n, x1, x2, y1, y2; scanf("%d %d %d", &n, &x, &y); for (int i = 0; i < n; ++i) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); xRangesLines.push_back({ std::min(x1, x2), std::max(x1, x2) }); yRangesLines.push_back({ std::min(y1, y2), std::max(y1, y2) }); } } int count(const int max, Ranges& rangesLines) { Lines lines({ 0, max }); for (const Range& range : rangesLines) { lines.push_back(range.first); lines.push_back(range.second); } Positions positionsStart; Positions positionsStop; preparePositions(rangesLines, positionsStart, positionsStop); Ranges ranges = prepareLines(lines); return getMaxDistance(ranges, positionsStart, positionsStop); } int main() { int x, y; Ranges xRangesLines; Ranges yRangesLines; readData(x, y, xRangesLines, yRangesLines); const long long int dx = count(x, xRangesLines); const long long int dy = count(y, yRangesLines); printf("%lld\n", dx * dy); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include <algorithm> #include <map> #include <set> #include <stdio.h> #include <vector> using Lines = std::vector<int>; using Range = std::pair<int, int>; using Ranges = std::vector<Range>; using Positions = std::multimap<int, int>; using LinesKey = std::tuple<int, int, int>; int getMaxDistance(const Ranges& ranges, const Positions& startPositions, const Positions& stopPositions) { std::map<LinesKey, int> linesSum; std::set<int> currentLines; for (const Range& range : ranges) { const auto rangeStart = startPositions.equal_range(range.first); for (auto it = rangeStart.first; it != rangeStart.second; ++it) { currentLines.insert(it->second); } const auto rangeStop = stopPositions.equal_range(range.first); for (auto it = rangeStop.first; it != rangeStop.second; ++it) { currentLines.erase(it->second); } if (currentLines.empty()) { const LinesKey key = std::make_tuple(0, 0, 0); linesSum[key] += range.second - range.first; } else { const LinesKey key = std::make_tuple(*currentLines.begin(), *currentLines.rbegin(), currentLines.size()); linesSum[key] += range.second - range.first; } } int max = 0; for (const auto& it : linesSum) { max = std::max(max, it.second); } return max; } void preparePositions(Ranges& ranges, Positions& positionsStart, Positions& positionsStop) { std::sort(ranges.begin(), ranges.end()); for (unsigned int i = 0; i < ranges.size(); ++i) { positionsStart.insert({ ranges[i].first, i }); positionsStop.insert({ ranges[i].second, i }); } } Ranges prepareLines(Lines& lines) { std::sort(lines.begin(), lines.end()); lines.erase(std::unique(lines.begin(), lines.end()), lines.end()); Ranges ranges; for (unsigned int i = 0; i < lines.size() - 1; ++i) { ranges.push_back({ lines[i], lines[i + 1] }); } return ranges; } void readData(int& x, int& y, Ranges& xRangesLines, Ranges& yRangesLines) { int n, x1, x2, y1, y2; scanf("%d %d %d", &n, &x, &y); for (int i = 0; i < n; ++i) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); xRangesLines.push_back({ std::min(x1, x2), std::max(x1, x2) }); yRangesLines.push_back({ std::min(y1, y2), std::max(y1, y2) }); } } int count(const int max, Ranges& rangesLines) { Lines lines({ 0, max }); for (const Range& range : rangesLines) { lines.push_back(range.first); lines.push_back(range.second); } Positions positionsStart; Positions positionsStop; preparePositions(rangesLines, positionsStart, positionsStop); Ranges ranges = prepareLines(lines); return getMaxDistance(ranges, positionsStart, positionsStop); } int main() { int x, y; Ranges xRangesLines; Ranges yRangesLines; readData(x, y, xRangesLines, yRangesLines); const long long int dx = count(x, xRangesLines); const long long int dy = count(y, yRangesLines); printf("%lld\n", dx * dy); return 0; } |