#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
struct point {
long long x, y;
point () {}
point (long long x, long long y) : x(x), y(y) {}
point operator + (point p) const {
return point(x + p.x, y + p.y);
}
point operator - (point p) const {
return point(x - p.x, y - p.y);
}
} a[maxn];
int ord[maxn];
long long cross(point p, point q) { return p.x * q.y - p.y * q.x; }
long long dot(point p, point q) { return p.x * q.x + p.y * q.y; }
bool inSegment(point a, point b, point c) {
return cross(c - a, b - a) == 0 &&
dot(a - b, a - b) >= max(dot(a - c, a - c), dot(c - b, c - b));
}
int side(point a, point b, point c) {
long long x = cross(b - a, c - a);
if(x > 0) return 1;
else if (x < 0) return -1;
else return 0;
}
bool intersect(point a, point b, point c, point d) {
if(side(a, b, c) * side(a, b, d) == -1 &&
side(c, d, a) * side(c, d, b) == -1) return true;
for(auto i : {c, d}) if(inSegment(a, b, i)) return true;
for(auto i : {a, b}) if(inSegment(c, d, i)) return true;
return false;
}
pair <long long, long long> sect(point a, point b, point c) {
point f = b - a;
long long p = cross(a, f) * c.x;
long long q = cross(c, f);
if(q < 0) { q *= -1; p *= -1; }
return make_pair(p, q);
}
point piv;
struct data {
int i, j;
data () {}
data (int i, int j) : i(i), j(j) {}
};
bool operator < (data p, data q) {
pair <long long, long long> e = sect(a[p.i], a[p.j], piv);
pair <long long, long long> f = sect(a[q.i], a[q.j], piv);
if(e.first * f.second == e.second * f.first) {
return make_pair(p.i, p.j) < make_pair(q.i, q.j);
} else {
return e.first * f.second < e.second * f.first;
}
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y;
ord[i] = i;
}
auto cmp = [&] (int i, int j) {
return cross(a[i], a[j]) > 0 ||
(cross(a[i], a[j]) == 0 && dot(a[i], a[i]) < dot(a[j], a[j]));
};
sort(ord, ord + n, cmp);
vector <int> res;
set <data> can;
int cur = 0;
while(cur < n) {
int x = ord[cur];
for(int i : {-1, 1}) {
int y = (x + i + n) % n;
if(cross(a[x], a[y]) < 0) {
can.erase(data(y, x));
}
}
piv = a[x];
if(cur == 0 || cross(a[ord[cur - 1]], a[ord[cur]]) != 0) {
//cout << "now at " << x + 1 << endl;
//for(auto g : can) {
// cout << g.i + 1 << ' ' << g.j + 1 << endl;
//}
if(can.empty() ||
!intersect(point(0, 0), a[x], a[can.begin() -> i],
a[can.begin() -> j])) res.emplace_back(x+1);
}
for(int i : {-1, 1}) {
int y = (x + i + n) % n;
if(cross(a[x], a[y]) > 0) {
can.insert(data(x, y));
}
}
cur++;
}
sort(res.begin(), res.end());
cout << res.size() << endl;
for(auto i : res) cout << i << " ";
cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 3 |
Correct |
7 ms |
512 KB |
Output is correct |
| 4 |
Correct |
8 ms |
512 KB |
Output is correct |
| 5 |
Incorrect |
23 ms |
1036 KB |
Output isn't correct |
| 6 |
Incorrect |
22 ms |
896 KB |
Output isn't correct |
| 7 |
Incorrect |
43 ms |
1656 KB |
Output isn't correct |
| 8 |
Incorrect |
19 ms |
768 KB |
Output isn't correct |
| 9 |
Correct |
15 ms |
768 KB |
Output is correct |
| 10 |
Incorrect |
23 ms |
1024 KB |
Output isn't correct |
| 11 |
Incorrect |
26 ms |
1152 KB |
Output isn't correct |
| 12 |
Incorrect |
30 ms |
896 KB |
Output isn't correct |
| 13 |
Incorrect |
65 ms |
2040 KB |
Output isn't correct |
| 14 |
Incorrect |
61 ms |
1528 KB |
Output isn't correct |
| 15 |
Incorrect |
71 ms |
1400 KB |
Output isn't correct |
| 16 |
Execution timed out |
151 ms |
2748 KB |
Time limit exceeded |
| 17 |
Execution timed out |
225 ms |
5740 KB |
Time limit exceeded |
| 18 |
Runtime error |
92 ms |
4344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
93 ms |
4344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
99 ms |
4344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
