#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=2e5;
int n, l, r;
long long x[mxN+1], y[mxN+1];
vector<int> v, s;
bool b[mxN];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
auto cp=[](int a, int b, int c) {
return (y[c]-y[a])*(x[b]-x[a])-(y[b]-y[a])*(x[c]-x[a]);
};
cin >> n;
for(int i=0; i<n; ++i) {
cin >> x[i] >> y[i];
if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l])
l=i;
if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r])
r=i;
}
int ic=cp((l+n-1)%n, l, (l+1)%n)>0?1:n-1;
for(; l^r; l=(l+ic)%n)
v.push_back(l);
v.push_back(r);
s={0, 1};
for(int i=2; i<v.size(); ++i) {
auto ul=[&]() {
while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<=0)
s.pop_back();
for(int j=i, c=cp(n, v[s.back()], v[i])<0; cp(n, v[s.back()], v[i])>=0||!c; ++i) {
if(i^j?cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0:cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0)
++c;
if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0)
--c;
}
};
if(!cp(n, v[i-1], v[i])&&(cp(n, v[i-2], v[i-1])<0)==(cp(v[i-2], v[i-1], v[i])<0))
s.pop_back();
else if(cp(n, v[i-1], v[i])>0&&(cp(n, v[i-2], v[i-1])>=0||cp(v[i-2], v[i-1], v[i])<0))
ul();
else if(cp(n, v[i-1], v[i])>=0&&cp(n, v[i-2], v[i-1])<0)
while(cp(n, v[s.back()], v[i])>=0)
++i;
else if(cp(n, v[i-1], v[i])<=0&&cp(n, v[i-2], v[i-1])>0&&cp(v[i-2], v[i-1], v[i])<0) {
while(cp(n, v[s.back()], v[i])<=0)
++i;
s.pop_back();
ul();
}
}
cout << s.size() << "\n";
for(int a : s)
b[v[a]]=1;
for(int i=0; i<n; ++i)
if(b[i])
cout << i+1 << " ";
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:22:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l])
~~~~~~~~~~~~^~~~~~~~~~~
circuit.cpp:24:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r])
~~~~~~~~~~~~^~~~~~~~~~~
circuit.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=2; i<v.size(); ++i) {
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 5 |
Runtime error |
5 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
6 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
8 ms |
1664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
5 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
4 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
5 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
6 ms |
1152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
7 ms |
1664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
10 ms |
2176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
10 ms |
2432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
14 ms |
2944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
23 ms |
4852 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
24 ms |
4600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
44 ms |
8560 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
47 ms |
8820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
51 ms |
8560 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
