#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define point pair <ld, ld>
#define X first
#define Y second
#define ll long long
#define ld long double
using namespace std;
const int MAXN = 100010;
struct line {
point A, B;
};
line lines[MAXN];
point ray;
set <line> s;
vector <point> ve;
vector <int> out;
int arr[MAXN];
int n;
const ld eps = 1e-6;
int ccw(point a, point b, point c) {
ld out = ((ld) a.X * (b.Y - c.Y)) +
((ld) b.X * (c.Y - a.Y)) +
((ld) c.X * (a.Y - b.Y));
if (out > 0.0) return 1;
if (out < 0.0) return -1;
return 0;
}
int ccw0(point a, point b) {
return ccw({0, 0}, a, b);
}
ld dist(point a) {
return (a.X * a.X) + (a.Y * a.Y);
}
point inter(line a, line b) {
ld ka = (a.A.Y - a.B.Y) / (a.A.X - a.B.X + eps);
ld kb = (b.A.Y - b.B.Y) / (b.A.X - b.B.X + eps);
ld la = a.A.Y - a.A.X * ka;
ld lb = b.A.Y - b.A.X * kb;
if (fabs(ka - kb) <= eps && fabs(la - lb) <= eps) {
if (dist(a.A) < dist(a.B)) return a.A;
return a.B;
}
ld x = (lb - la) / (ka - kb + eps);
return {x, ka * x + la};
}
bool operator< (const line &x, const line &y) {
point a = x.A, b = x.B;
point c = y.A, d = y.B;
if (ccw0(a, b) < 0) swap(a, b);
if (ccw0(c, d) < 0) swap(c, d);
if (ccw(a, b, c) <= 0 && ccw(a, b, d) <= 0) return 1;
if (ccw(a, b, c) >= 0 && ccw(a, b, d) >= 0) return 0;
point ix = inter({a, b}, {{0, 0}, ray});
point iy = inter({c, d}, {{0, 0}, ray});
ld dx = dist(ix);
ld dy = dist(iy);
return dx < dy;
}
bool cmp(int aa, int bb) {
point a = ve[aa];
point b = ve[bb];
if (ccw0(a, b) == 0) {
ld da = dist(a);
ld db = dist(b);
return da < db;
}
return ccw0(a, b) > 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> n;
REP(i, n) {
int a, b;
cin >> a >> b;
ve.push_back({a, b});
arr[i] = i;
}
//cout << fixed << setprecision(3) << endl;
sort(arr, arr + n, cmp);
REP(ind, n) {
int i = arr[ind];
//cout << i + 1 << endl;
point x = ve[i];
ray = x;
for (int t : {-1, 1}) {
int j = (i + t + n) % n;
point y = ve[j];
if (cmp(i, j)) {
line tr = {x, y};
s.insert(tr);
} else {
line tr = {y, x};
s.erase(tr);
}
}
ld dx = dist(x), dy = 1e13;
//cout << dx << " " << dy << endl;
if (s.size()) {
line tr = *s.begin();
point y = inter(tr, {{0, 0}, ray});
//cout << ray.X << " " << ray.Y << endl;
//cout << tr.A.X << " " << tr.A.Y << " - " << tr.B.X << " " << tr.B.Y << endl;
//cout << y.X << " " << y.Y << endl;
dy = dist(y);
}
//cout << dx << " " << dy << endl;
if (dx - dy <= 0.001) {
out.push_back(i);
}
}
//cout << endl;
sort(out.begin(), out.end());
cout << out.size() << "\n";
for (int x : out) cout << x + 1 << " ";
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
484 KB |
Output isn't correct |
| 3 |
Correct |
10 ms |
904 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
1072 KB |
Output isn't correct |
| 5 |
Incorrect |
29 ms |
1200 KB |
Output isn't correct |
| 6 |
Incorrect |
39 ms |
1252 KB |
Output isn't correct |
| 7 |
Incorrect |
63 ms |
2084 KB |
Output isn't correct |
| 8 |
Incorrect |
33 ms |
2084 KB |
Output isn't correct |
| 9 |
Incorrect |
28 ms |
2084 KB |
Output isn't correct |
| 10 |
Incorrect |
35 ms |
2084 KB |
Output isn't correct |
| 11 |
Incorrect |
33 ms |
2084 KB |
Output isn't correct |
| 12 |
Incorrect |
54 ms |
2084 KB |
Output isn't correct |
| 13 |
Incorrect |
99 ms |
2820 KB |
Output isn't correct |
| 14 |
Execution timed out |
158 ms |
5804 KB |
Time limit exceeded |
| 15 |
Execution timed out |
162 ms |
5804 KB |
Time limit exceeded |
| 16 |
Execution timed out |
330 ms |
5804 KB |
Time limit exceeded |
| 17 |
Execution timed out |
410 ms |
7028 KB |
Time limit exceeded |
| 18 |
Runtime error |
39 ms |
8052 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
57 ms |
8900 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
44 ms |
8956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
