Submission #226360

#TimeUsernameProblemLanguageResultExecution timeMemory
226360BruteforcemanPrinted Circuit Board (CEOI12_circuit)C++11
35 / 100
1096 ms5368 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int n; struct point { long long x, y; point () {} point (long long x, long long y) : x(x), y(y) {} point operator + (point p) const { return point(x + p.x, y + p.y); } point operator - (point p) const { return point(x - p.x, y - p.y); } } a[maxn]; int ord[maxn]; long long cross(point p, point q) { return p.x * q.y - p.y * q.x; } long long dot(point p, point q) { return p.x * q.x + p.y * q.y; } bool inSegment(point a, point b, point c) { return cross(c - a, b - a) == 0 && dot(a - b, a - b) >= max(dot(a - c, a - c), dot(c - b, c - b)); } int side(point a, point b, point c) { long long x = cross(b - a, c - a); if(x > 0) return 1; else if (x < 0) return -1; else return 0; } bool intersect(point a, point b, point c, point d) { if(side(a, b, c) * side(a, b, d) == -1 && side(c, d, a) * side(c, d, b) == -1) return true; for(auto i : {c, d}) if(inSegment(a, b, i)) return true; for(auto i : {a, b}) if(inSegment(c, d, i)) return true; return false; } double sect(point a, point b, point c) { point f = b - a; return double(c.x * cross(a, f)) / cross(c, f); } int main() { cin >> n; for(int i = 0; i < n; i++) { cin >> a[i].x >> a[i].y; ord[i] = i; } auto cmp = [&] (int i, int j) { return cross(a[i], a[j]) > 0 || (cross(a[i], a[j]) == 0 && dot(a[i], a[i]) < dot(a[j], a[j])); }; sort(ord, ord + n, cmp); vector <int> res; set <pair <int, int>> can; int cur = 0; while(cur < n) { int x = ord[cur]; for(int i : {-1, 1}) { int y = (x + i + n) % n; if(cross(a[x], a[y]) < 0) { can.erase(make_pair(y, x)); // cout << "erase " << y+1 << " " << x+1 << endl; } } if(cur == 0 || cross(a[ord[cur - 1]], a[ord[cur]]) != 0) { bool bad = false; double ox = INT_MAX; for(auto i : can) { ox = min(ox, sect(a[i.first], a[i.second], a[x])); } if(a[x].x <= ox) res.emplace_back(x+1); // cout << "check " << x << endl; } for(int i : {-1, 1}) { int y = (x + i + n) % n; if(cross(a[x], a[y]) > 0) { can.insert(make_pair(x, y)); // cout << "insert " << x+1 << " " << y+1 << endl; } } cur++; } sort(res.begin(), res.end()); cout << res.size() << endl; for(auto i : res) cout << i << " "; cout << endl; return 0; }

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:66:12: warning: unused variable 'bad' [-Wunused-variable]
       bool bad = false;
            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...