Submission #1236213

#TimeUsernameProblemLanguageResultExecution timeMemory
1236213abc864197532Printed Circuit Board (CEOI12_circuit)C++20
80 / 100
222 ms61036 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) ((int)a.size()) #ifdef Doludu template <typename T> ostream& operator << (ostream &o, vector <T> vec) { o << "{"; int f = 0; for (T i : vec) o << (f++ ? " " : "") << i; return o << "}"; } void bug__(int c, auto ...a) { cerr << "\e[1;" << c << "m"; (..., (cerr << a << " ")); cerr << "\e[0m" << endl; } #define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x) #define bug(x...) bug_(32, x) #define bugv(x...) bug_(36, vector(x)) #define safe bug_(33, "safe") #else #define bug(x...) void(0) #define bugv(x...) void(0) #define safe void(0) #endif const int mod = 998244353, N = 500005; int sign(ll x) { return clamp(x, -1ll, 1ll); } template <typename T> struct P { T x, y; P (T _x = 0, T _y = 0) : x(_x), y(_y) {} P<T> operator + (P<T> o) { return P<T>(x + o.x, y + o.y);} P<T> operator - (P<T> o) { return P<T>(x - o.x, y - o.y);} P<T> operator * (T k) {return P<T>(x * k, y * k);} P<T> operator / (T k) {return P<T>(x / k, y / k);} T operator * (P<T> o) {return x * o.x + y * o.y;} T operator ^ (P<T> o) {return x * o.y - y * o.x;} friend ostream& operator << (ostream &o, P<T> a) { return o << "(" << a.x << ", " << a.y << ")"; } bool operator == (P<T> o) { return sign(x - o.x) == 0 && sign(y - o.y) == 0;} }; using Pt = P<ll>; struct Line { Pt a, b; }; int ori(Pt o, Pt a, Pt b) { return sign((o - a) ^ (o - b)); } ll abs2(Pt o) { return o * o; } struct Event { Pt d; int type; Line ls; bool operator < (const Event &o) { if ((d ^ o.d) == 0) return type < o.type; return (d ^ o.d) > 0; } }; int main() { ios::sync_with_stdio(false), cin.tie(0); int n; cin >> n; vector <Pt> pts(n); for (int i = 0; i < n; ++i) { cin >> pts[i].x >> pts[i].y; } vector <Event> eve; // -1 -> insert, [0, n) -> query, n -> delete for (int i = 0; i < n; ++i) { int ni = i + 1 == n ? 0 : i + 1; Pt a = pts[i], b = pts[ni]; if (sign(a ^ b) < 0) swap(a, b); else if (sign(a ^ b) == 0 && abs2(b) < abs2(a)) swap(a, b); eve.pb({a, -1, Line{a, b}}); eve.pb({b, n, Line{a, b}}); eve.pb({pts[i], i, Line{pts[i], pts[i]}}); } sort(all(eve)); auto cmp = [&](Line a, Line b) { if (a.a == b.a) { int x = ori(b.b, a.a, a.b); if (x) return x == -1; return false; } else if ((a.a ^ b.a) > 0) { int x = ori(b.a, a.a, a.b); if (x) return x == -1; x = ori(b.b, a.a, a.b); return x == -1; } else if ((a.a ^ b.a) < 0) { int x = ori(a.a, b.a, b.b); if (x) return x == 1; x = ori(a.b, b.a, b.b); return x == 1; } else { return abs2(a.a) < abs2(b.a); } }; set <Line, decltype(cmp)> S(cmp); vector <int> ans; for (auto [d, type, l] : eve) { if (type == -1) { S.insert(l); } else if (type == n) { S.erase(l); } else { assert(!S.empty()); auto [a, b] = *S.begin(); if (a == pts[type] || b == pts[type]) { if (sign(a ^ b) == 0 && b == pts[type]) continue; ans.pb(type); } } } sort(all(ans)); cout << sz(ans) << "\n"; for (int i = 0; i < sz(ans); ++i) cout << ans[i] + 1 << " \n"[i + 1 == sz(ans)]; }
#Verdict Execution timeMemoryGrader output
Fetching results...