#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 1e5 + 5;
int n;
int X[maxn];
int Y[maxn];
map<ii, int> M;
vector<int> ans;
int sol[maxn];
ii P[maxn];
ll cross(ii p1, ii p2, ii p3) {return (ll)p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);}
ll dist(ii p1) {
return (ll)p1.x * p1.x + p1.y * p1.y;
}
struct line {
ii pL, pR;
friend bool operator<(line l1, line l2) {
if(dist(l1.pR) == dist(l2.pR))
return dist(l1.pL) < dist(l2.pL);
return dist(l1.pR) < dist(l2.pR);
}
};
struct event {
line l;
ii p;
int open;
friend bool operator<(event a, event b) {
if(a.p == b.p) return a.open > b.open;
if(cross({0, 0}, a.p, b.p) == 0) return a.p.x > b.p.x;
return cross({0, 0}, a.p, b.p) < 0;
}
};
int main() {
scanf("%d", &n);
for(int i = 0;i < n;i++)
scanf("%d%d", X + i, Y + i), M[{X[i], Y[i]}] = i, P[i] = {X[i], Y[i]};
X[n] = X[0];
Y[n] = Y[0];
vector<event> sweep;
for(int i = 0;i < n;i++) {
line l;
l.pL = {X[i], Y[i]};
l.pR = {X[i + 1], Y[i + 1]};
if(cross({0, 0}, l.pL, l.pR) > 0) swap(l.pL, l.pR);
event e;
e.l = l, e.p = l.pL, e.open = 1;
sweep.pb(e);
e.p = l.pR, e.open = 0;
sweep.pb(e);
}
sort(all(sweep));
set<line> s;
line l1, l2;
l1.pL = P[3], l1.pR = P[4];
l2.pL = P[1], l2.pR = P[2];
for(auto e : sweep) {
if(e.open == 1) {
if(s.size() == 0) sol[M[e.p]] = 1;
else {
line l = *s.begin();
if(e.l < l) sol[M[e.p]] = 1;
}
s.insert(e.l);
} else {
if(s.size() == 0) sol[M[e.p]] = 1;
else {
line l = *s.begin();
if(l.pR == e.p) sol[M[e.p]] = 1;
s.erase(s.find(e.l));
}
}
}
for(int i = 0;i < n;i++)
if(sol[i] == 1) ans.pb(i);
printf("%d\n", (int)ans.size());
for(int i : ans) printf("%d ", i + 1);
printf("\n");
return 0;
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
circuit.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d%d", X + i, Y + i), M[{X[i], Y[i]}] = i, P[i] = {X[i], Y[i]};
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Runtime error |
3 ms |
852 KB |
Execution killed with signal 6 |
| 3 |
Correct |
3 ms |
872 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
1000 KB |
Output isn't correct |
| 5 |
Runtime error |
10 ms |
3536 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
9 ms |
3528 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
17 ms |
6332 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
8 ms |
2960 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
7 ms |
3148 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
8 ms |
3536 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
10 ms |
3776 KB |
Execution killed with signal 6 |
| 12 |
Incorrect |
16 ms |
3948 KB |
Output isn't correct |
| 13 |
Runtime error |
25 ms |
9216 KB |
Execution killed with signal 6 |
| 14 |
Incorrect |
32 ms |
7496 KB |
Output isn't correct |
| 15 |
Incorrect |
41 ms |
8496 KB |
Output isn't correct |
| 16 |
Runtime error |
84 ms |
28860 KB |
Execution killed with signal 6 |
| 17 |
Runtime error |
91 ms |
29032 KB |
Execution killed with signal 6 |
| 18 |
Runtime error |
46 ms |
18608 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
43 ms |
18508 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
83 ms |
18636 KB |
Execution killed with signal 11 |
