#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
using namespace std;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
const int N = 1e5 + 10;
const ld INF = 1e13;
const ld DIFF = 1e-7;
int n, on[N], CNT;
ld ang = 1;
ld abs2(ld a){
if(a < 0) return -a;
return a;
}
bool eq(ld a, ld b){
return abs2(a - b) <= DIFF;
}
struct line{
ld a, b;
bool ver;
line(ld x1, ld y1, ld x2, ld y2){
ver = false;
if(x1 != x2){
a = (y2 - y1) / (x2 - x1);
b = y1 - a * x1;
} else {
a = x1;
b = 0;
ver = true;
}
}
};
ld inter(line a){if(a.ver) return a.a; else if(eq(ang, a.a)) return -INF; return a.b / (ang - a.a); }
bool operator< (const line &a, const line &b) { return inter(a) < inter(b); }
struct dot{
ld x, y;
dot(){};
dot(int a, int b){ x = a; y = b; };
bool operator< (dot b){ return (y / x) > (b.y / b.x) + DIFF || (eq(y / x, b.y / b.x) && x > b.x); };
};
dot pol[N];
vector<pair<dot, int>> cs;
vector<line> ln;
vector<int> edge[N], ans;
set<line> s;
bool comp(pair<dot, int> a, pair<dot, int> b){ return a.X < b.X; }
void debug(line x){
printf("(%.3LF, %.3LF) %.3Lf\n", x.a, x.b, inter(x));
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
ld x, y;
scanf("%Lf%Lf", &x, &y);
cs.pb({dot(x, y), i});
pol[i] = dot(x, y);
}
for(int i = 0; i < n; i++){
edge[i].pb(ln.size());
edge[(i + 1) % n].pb(ln.size());
ln.pb(line(pol[i].x, pol[i].y, pol[(i + 1) % n].x, pol[(i + 1) % n].y));
}
sort(cs.begin(), cs.end(), comp);
for(pair<dot, int> par : cs){
dot d = par.X;
int ind = par.Y;
//printf("%d\n", ind);
ang = d.y / d.x;
for(int i : edge[ind])
if(on[i]){
s.erase(ln[i]);
//if(i == 2) debug(ln[i]);
}
if(s.empty() || d.x + DIFF < inter(*s.begin())){
ans.pb(ind);
}
if(!s.empty() && ind == 1){
line l = *(s.begin());
//debug(l);
}
for(int i : edge[ind])
if(!on[i]){
s.insert(ln[i]);
on[i] = 1;
}
}
sort(ans.begin(), ans.end());
printf("%d\n", (int) ans.size());
for(int i = 0; i < (int) ans.size(); i++) printf("%d ", ans[i] + 1);
printf("\n");
return 0;
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:107:9: warning: variable 'l' set but not used [-Wunused-but-set-variable]
107 | line l = *(s.begin());
| ^
circuit.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
circuit.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%Lf%Lf", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2660 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
2784 KB |
Output isn't correct |
| 3 |
Correct |
5 ms |
3220 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3348 KB |
Output is correct |
| 5 |
Incorrect |
16 ms |
4812 KB |
Output isn't correct |
| 6 |
Incorrect |
16 ms |
4864 KB |
Output isn't correct |
| 7 |
Incorrect |
31 ms |
7004 KB |
Output isn't correct |
| 8 |
Incorrect |
14 ms |
4168 KB |
Output isn't correct |
| 9 |
Incorrect |
19 ms |
4580 KB |
Output isn't correct |
| 10 |
Incorrect |
18 ms |
4812 KB |
Output isn't correct |
| 11 |
Incorrect |
23 ms |
4980 KB |
Output isn't correct |
| 12 |
Incorrect |
23 ms |
6924 KB |
Output isn't correct |
| 13 |
Incorrect |
47 ms |
8556 KB |
Output isn't correct |
| 14 |
Incorrect |
48 ms |
11248 KB |
Output isn't correct |
| 15 |
Incorrect |
59 ms |
12728 KB |
Output isn't correct |
| 16 |
Execution timed out |
137 ms |
22836 KB |
Time limit exceeded |
| 17 |
Execution timed out |
202 ms |
22956 KB |
Time limit exceeded |
| 18 |
Runtime error |
61 ms |
24880 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
50 ms |
24912 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
54 ms |
25252 KB |
Execution killed with signal 11 |
