Submission #701608

#TimeUsernameProblemLanguageResultExecution timeMemory
701608CyanmondRoads (CEOI20_roads)C++17
0 / 100
162 ms16888 KiB
#include <bits/stdc++.h> using i64 = long long; struct Point { i64 x; i64 y; }; struct Segment { Point a; Point b; double eval(i64 x) { assert(a.x <= b.x); if (a.x == b.x) { return a.y; } else { double ac = a.y * (b.x - x); double bc = b.y * (x - a.x); return (ac + bc) / (b.x - a.x); } } }; constexpr i64 maxC = 2000000; int main() { auto compSegment = [](Segment a, Segment b) { // not cross bool isSwapped = false; if (a.a.x < b.a.x) { std::swap(a, b); isSwapped = true; } i64 s = a.a.y; const auto t = b.eval(a.a.x); if (double(s) < t) { return true xor isSwapped; } else { return false xor isSwapped; } }; auto compPoint = [](Point a, Point b) { // tokuni iminasi return a.x * maxC + a.y < b.x * maxC + b.y; }; int N; std::cin >> N; std::vector<Segment> segments(N); for (auto &[as, bs] : segments) { auto &[ax, ay] = as; auto &[bx, by] = bs; std::cin >> ax >> ay >> bx >> by; } // std::map<i64, std::vector<int>> addList, eraseList; std::map<i64, std::vector<std::pair<int, int>>> eventList; for (int i = 0; i < N; ++i) { auto &[as, bs] = segments[i]; if (as.x > bs.x) { std::swap(as, bs); } if (as.x == bs.x) { assert(as.y != bs.y); if (as.y > bs.y) { std::swap(as, bs); } } eventList[as.x].push_back({i, true}); eventList[bs.x].push_back({i, false}); } std::map<Point, std::pair<int, bool>, decltype(compPoint)> indexList(compPoint); for (int i = 0; i < N; ++i) { indexList[segments[i].a] = {i, true}; indexList[segments[i].b] = {i, false}; } std::set<Segment, decltype(compSegment)> segmentSet(compSegment); std::vector<Point> safePoint(N); std::vector<std::pair<Point, Point>> answer; Point safeMi; bool isFirst = true; for (auto &[xVal, vec] : eventList) { std::sort(vec.begin(), vec.end(), [](auto &a, auto &b) { return a.second > b.second; // add pr }); for (const auto &[i, type] : vec) { if (type) { auto itr = segmentSet.insert(segments[i]).first; if (itr == segmentSet.begin()) { if (isFirst) { safeMi = segments[i].a; isFirst = false; } else { answer.push_back({segments[i].a, safeMi}); safeMi = segments[i].a; } safePoint[i] = segments[i].a; if (segments[i].a.x == segments[i].b.x) { safePoint[i] = segments[i].b; // ok ? } continue; } --itr; answer.push_back({segments[i].a, safePoint[indexList[itr->a].first]}); safePoint[indexList[itr->a].first] = segments[i].a; safePoint[i] = segments[i].a; if (segments[i].a.x == segments[i].b.x) { safePoint[i] = segments[i].b; // ok ? } } else { auto itr = segmentSet.find(segments[i]); itr = segmentSet.erase(itr); if (itr == segmentSet.begin()) { safeMi = segments[i].b; continue; } --itr; safePoint[indexList[itr->a].first] = segments[i].b; } } } assert(answer.size() == N - 1); for (const auto &[ap, bp] : answer) { std::cout << ap.x << ' ' << ap.y << ' ' << bp.x << ' ' << bp.y << std::endl; } }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from roads.cpp:1:
roads.cpp: In function 'int main()':
roads.cpp:126:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<Point, Point> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  126 |     assert(answer.size() == N - 1);
      |            ~~~~~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...