Submission #54949

#TimeUsernameProblemLanguageResultExecution timeMemory
54949linkretPrinted Circuit Board (CEOI12_circuit)C++14
75 / 100
198 ms29548 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define f first #define s second const int maxn = 1 << 17; struct line { pii a, b; }; int n, k; pair<pii, int> p[maxn]; pii org[maxn]; int arr[maxn]; vector<line> add[maxn]; vector<line> rem[maxn]; vector<pair<pii, int> > query[maxn]; vector<int> ans; ll ccw(pii a, pii b, pii c) { return ll(a.f) * (b.s - c.s) + ll(b.f) * (c.s - a.s) + ll(c.f) * (a.s - b.s); } bool comp(pair<pii, int> a, pair<pii, int> b) { ll c = ccw(pii(0, 0), a.f, b.f); if(c == 0) return a.s < b.s; return c > 0; } bool operator==(line x, line y) { return x.a == y.a && x.b == y.b; } bool operator<(line x, line y) { if(x == y) return false; // if(x.a == y.a) // return x.b < y.b; // if(x.a == y.b) // return x.b < y.a; // if(x.b == y.a) // return x.a < y.b; // if(x.b == y.b) // return x.a < y.a; bool ret = false; // ll sum = ccw(pii(0, 0), y.a, y.b) // + ccw(pii(0, 0), y.b, x.b) // + ccw(pii(0, 0), x.b, x.a) // + ccw(pii(0, 0), x.a, y.a); ll sum = ccw(x.a, y.a, x.b) + ccw(x.b, y.a, y.b); if(sum == 0) { if(x.a.s == y.a.s) return x.a.f < y.a.f; return x.a.f < y.a.f; } ret = sum > 0; // ll xa, xb, ya, yb; // xa = ccw(x.a, x.b, y.a); // xb = ccw(x.a, x.b, y.b); // ya = ccw(y.a, y.b, x.a); // yb = ccw(y.a, y.b, x.b); // if(!xa && !xb && !ya && !yb) { // if(x.a.s == y.a.s) // return x.a.f < y.a.f; // return x.a.f < y.a.f; // } // // cout << "values: " << xa << " " << xb << " " << ya << " " << yb << endl; // if((xa > 0) == (xb > 0) || !xa || !xb) { // if(!xa) // ret = xb < 0; // else // ret = xa < 0; // } else if ((ya > 0) == (yb > 0) || !ya || !yb) { // if(!ya) // ret = yb > 0; // else // ret = ya > 0; // } else { // // cout << x.a.f << "," << x.a.s << "-" << x.b.f << "," << x.b.s << " " << y.a.f << "," << y.a.s << "-" << y.b.f << "," << y.b.s << endl; // assert(false); // } // cout << ret << " " << ": " << x.a.f << "," << x.a.s << "-" << x.b.f << "," << x.b.s << " " << y.a.f << "," << y.a.s << "-" << y.b.f << "," << y.b.s << endl; // cout << endl; return ret; } void sweep() { multiset<line> st; for(int t = 1; t <= k; t++) { for(const line &i : add[t]) { st.insert(i); } // if(t == 102) { // for(auto i : st) // cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " "; // cout << endl; // } // assert(!st.empty()); line f = *st.begin(); sort(query[t].begin(), query[t].end()); for(const pair<pii, int> &i : query[t]) { // assert(!st.empty()); if(ccw(f.a, f.b, i.f) == 0) { ans.push_back(i.s); } break; } // cout << "trebam izbrisat: "; // for(const line &i : rem[t]) { // cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " "; // } // cout << endl; for(const line &i : rem[t]) { // cout<<(i < i)<<endl; auto it = st.find(i); // assert(it != st.end()); // if(it != st.end()) st.erase(it); } // cout << "success "; // cout << t << ": "; // for(line i : st) { // cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " "; // } // cout << endl; } } void add_edge(int i, int j, int x, int y) { if(i < j) { add[i].push_back(line{org[x], org[y]}); rem[j].push_back(line{org[x], org[y]}); } else { add[j].push_back(line{org[y], org[x]}); rem[i].push_back(line{org[y], org[x]}); } } void compress() { sort(p, p + n, comp); for(int i = 0; i < n; i++) { if(i == 0 || ccw(pii(0, 0), p[i].f, p[i - 1].f)) k++; arr[p[i].s] = k; query[k].push_back(p[i]); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // while(true) { // int a, b, c, d; // cin >> a >> b >> c >> d; // line x{pii(a, b), pii(c, d)}; // int aa, bb, cc, dd; // cin >> aa >> bb >> cc >> dd; // line y{pii(aa, bb), pii(cc, dd)}; // cout << (x < y) << endl; // } cin >> n; for(int i = 0; i < n; i++) { pii tmp; cin >> tmp.f >> tmp.s; p[i].f = tmp; p[i].s = i; org[i] = p[i].f; } compress(); // for(int i = 0; i < n; i++) { // cout << arr[i] << " "; // } // cout << endl; for(int i = 0; i < n - 1; i++) add_edge(arr[i], arr[i + 1], i, i + 1); add_edge(arr[n - 1], arr[0], n - 1, 0); // for(int i = 1; i <= n; i++) { // cout << i << ": "; // for(line j : add[i]) { // cout << j.a.f << "," << j.a.s << "-" << j.b.f << "," << j.b.s << " "; // } // cout << endl; // } // cout << endl; // cout << arr[21] << " " << arr[22] << endl; sweep(); cout << ans.size() << endl; sort(ans.begin(), ans.end()); for(int i : ans) { cout << i + 1 << " "; } cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...