#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);
map<pair<int, int>, int> mini;
vector<int> xxx(n), yyy(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);
int xx = x, yy = y;
xx /= __gcd((int) x, (int) y);
yy /= __gcd((int) x, (int) y);
xxx[i] = x;
yyy[i] = y;
if (mini[{xx, yy}] == 0) mini[{xx, yy}] = x;
else mini[{xx, yy}] = min(mini[{xx, yy}], (int) x);
}
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;
}
}
vector<int> newAns;
for (int ind : ans) {
int g = __gcd(xxx[ind], yyy[ind]);
if (mini[{xxx[ind] / g, yyy[ind] / g}] == xxx[ind]) newAns.push_back(ind);
}
ans = newAns;
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:121:9: warning: variable 'l' set but not used [-Wunused-but-set-variable]
121 | 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:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%Lf%Lf", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
2900 KB |
Output isn't correct |
| 3 |
Correct |
6 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
7 ms |
3668 KB |
Output is correct |
| 5 |
Incorrect |
23 ms |
5388 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
5388 KB |
Output isn't correct |
| 7 |
Incorrect |
41 ms |
8200 KB |
Output isn't correct |
| 8 |
Incorrect |
21 ms |
4624 KB |
Output isn't correct |
| 9 |
Incorrect |
17 ms |
5112 KB |
Output isn't correct |
| 10 |
Incorrect |
20 ms |
5388 KB |
Output isn't correct |
| 11 |
Incorrect |
23 ms |
5636 KB |
Output isn't correct |
| 12 |
Correct |
32 ms |
8200 KB |
Output is correct |
| 13 |
Incorrect |
68 ms |
10192 KB |
Output isn't correct |
| 14 |
Incorrect |
60 ms |
13620 KB |
Output isn't correct |
| 15 |
Incorrect |
80 ms |
15728 KB |
Output isn't correct |
| 16 |
Execution timed out |
174 ms |
28776 KB |
Time limit exceeded |
| 17 |
Execution timed out |
255 ms |
28864 KB |
Time limit exceeded |
| 18 |
Execution timed out |
106 ms |
40596 KB |
Time limit exceeded |
| 19 |
Execution timed out |
106 ms |
40584 KB |
Time limit exceeded |
| 20 |
Execution timed out |
126 ms |
40556 KB |
Time limit exceeded |
