Submission #54942

#TimeUsernameProblemLanguageResultExecution timeMemory
54942paulicaPrinted Circuit Board (CEOI12_circuit)C++14
30 / 100
317 ms8964 KiB
#include <bits/stdc++.h> using namespace std; #define _ << " _ " << #define TRACE(x) cout << #x << " = " << x << endl #define fi first #define se second typedef pair<int, int> pii; typedef long long ll; typedef long double ld; const int MaxN = 1e5 + 10; int n, x[MaxN], y[MaxN]; pair<int, int> line[MaxN]; ll ccw(int i, int j, int k) { return (ll)x[i] * (y[j] - y[k]) + (ll)x[j] * (y[k] - y[i]) + (ll)x[k] * (y[i] - y[j]); } ll dist(int i) { return (ll)x[i] * x[i] + (ll)y[i] * y[i]; } bool equ(int i, int j) { return (ll)y[i] * x[j] == (ll)y[j] * x[i]; } bool pointCmp(int i, int j) { if (equ(i, j)) return dist(i) < dist(j); return (ll)y[i] * x[j] < (ll)y[j] * x[i]; } bool eventCmp(pair<pii, int>& a, pair<pii, int>& b) { if (equ(a.fi.fi, b.fi.fi) && a.se != b.se) return a.se < b.se; return pointCmp(a.fi.fi, b.fi.fi); } void printLine(int i) {cout << line[i].fi + 1 << "-" << line[i].se + 1 << " ";} ld intersec(int i, int j) { int a = line[j].fi, b = line[j].se; if (x[a] == x[b]) return x[a]; ld k1 = (ld)y[i] / x[i]; ld k2 = (ld)(y[a] - y[b]) / (x[a] - x[b]); ld l = (ld)((ll)x[a] * y[b] - (ll)x[b] * y[a]) / (x[a] - x[b]); if (k1 - k2 == 0) return min(x[a], x[b]); /* cout << "intersec " << i + 1 << " "; printLine(j); cout << l / (k1 -k2) << endl; */ return l / (k1 - k2); }//*/ bool above(int i, int j) { // return ccw(line[j].fi, i, line[j].se) > 0; if (i == line[j].fi || i == line[j].se) return false; return intersec(i, j) < (ld)x[i]; } int mod(int i) { if (i >= n) return i - n; return i; } struct lineCmp { bool operator()(int i, int j) { if (i == j) return false; bool ret; //cout << line[i].se + 1 << " " << line[j].se + 1 << " " << pointCmp(line[i].se, line[j].se) << endl; int a1 = line[i].fi, b1 = line[i].se; int a2 = line[j].fi, b2 = line[j].se; if ((mod(i + 1) == j)) ret = x[i] < x[mod(i + 2)]; else if ((mod(j + 1) == i)) ret = x[mod(i + 1)] < x[j]; /* else if (pointCmp(line[i].se, line[j].se)) { cout << "!!!\n"; ret = above(line[j].fi, i); } else ret = above(line[j].se, i); */ /* else { ld min1 = min(intersec(line[j].fi, i), intersec(line[j].se, i)); ld min2 = min(intersec(line[i].fi, j), intersec(line[i].se, j)); ret = min1 < min2; } */ else if (pointCmp(a1, a2) && pointCmp(a2, b1)) ret = above(a2, i); else if (pointCmp(a1, b2) && pointCmp(b2, b1)) ret = above(b2, i); else if (pointCmp(a2, a1) && pointCmp(a1, b2)) ret = !above(a1, j); else if (pointCmp(a2, b1) && pointCmp(b1, b2)) ret = !above(b2, j); /* cout << "cmp "; printLine(i); printLine(j); cout << ret << endl << endl; cin.get(); */ return ret; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; vector<pair<pii, int>> events; for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; events.push_back({{i, i}, 1}); } for (int i = 0; i < n; i++) { if (i == n - 1) line[i] = {i, 0}; else line[i] = {i, i + 1}; if (pointCmp(line[i].se, line[i].fi)) swap(line[i].fi, line[i].se); events.push_back({{line[i].fi, i}, 0}); events.push_back({{line[i].se, i}, 2}); } // lineCmp c; //cout << c(6, 8) << endl; sort(events.begin(), events.end(), eventCmp); set<int, lineCmp> lines; vector<int> sol; for (auto ev : events) { if (ev.se == 0) { lines.insert(ev.fi.se); //int l = ev.fi.se; //cout << "+ "; //printLine(l); //cout << endl; } else if (ev.se == 1) { int i = ev.fi.se; // cout << endl; // TRACE(i + 1); // for (int l : lines) cout << line[l].fi + 1 << "-" << line[l].se + 1 << " "; cout << endl; int j = *lines.begin(); // cout << line[j].fi + 1 << "-" << line[j].se + 1 << endl; // if (intersec(i, j) >= x[i]) if (!above(i, j)) sol.push_back(i); // if (!above(i, j)) cout << "yes\n"; // cout << endl; } else { // cout << "!" << (lines.find(ev.fi.se) != lines.end()) << "!\n"; // cout << lines.size() << " -> "; lines.erase(ev.fi.se); // cout << lines.size() << " "; // cout << "- "; // printLine(ev.fi.se); // cout << " " << ev.fi.se << endl; } } sort(sol.begin(), sol.end()); cout << sol.size() << "\n"; for (int i : sol) cout << i + 1 << " "; return 0; }

Compilation message (stderr)

circuit.cpp: In member function 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const int&; _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = lineCmp; _Alloc = std::allocator<int>]':
circuit.cpp:79:14: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
         bool ret;
              ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...