#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second
const int maxn = 1 << 18, inf = 1e9;
struct line {
int a, b;
};
int n, k;
pair<pii, int> p[maxn];
pii org[maxn];
int arr[maxn];
int addlen[maxn], remlen[maxn];
line *add[maxn];
line *rem[maxn];
pair<pii, int> query[maxn];
vector<int> ans;
pii zero;
ll ccw(const pii &a, const pii &b, const pii &c) {
return ll(a.f) * (b.s - c.s) + ll(b.f) * (c.s - a.s) + ll(c.f) * (a.s - b.s);
}
bool comp(pair<pii, int> a, pair<pii, int> b) {
ll c = ccw(zero, a.f, b.f);
if(c == 0)
return a.s < b.s;
return c > 0;
}
bool operator<(line x, line y) {
const pii &xa = org[x.a];
const pii &xb = org[x.b];
const pii &ya = org[y.a];
const pii &yb = org[y.b];
if(xa == ya && xb == yb)
return false;
ll sum = ccw(xa, ya, xb) + ccw(xb, ya, yb);
if(!sum) {
if(xa.s == ya.s)
return xa.f < ya.f;
return xa.f < ya.f;
}
return sum > 0;
}
void sweep() {
multiset<line> st;
for(int t = 1; t <= k; t++) {
for(int i = 0; i < addlen[t]; i++) {
st.insert(add[t][i]);
}
if(!st.empty()) {
line f = *st.begin();
auto mnm = query[t];
if(ccw(org[f.a], org[f.b], mnm.f) == 0) {
ans.push_back(mnm.s);
}
}
for(int i = 0; i < remlen[t]; i++) {
auto it = st.find(rem[t][i]);
st.erase(it);
}
}
}
void add_edge(int i, int j, int x, int y, bool b) {
if(i < j) {
if(b) {
addlen[i]++;
remlen[j]++;
} else {
add[i][addlen[i]++] = line{x, y};
rem[j][remlen[j]++] = line{x, y};
}
} else {
if(b) {
addlen[j]++;
remlen[i]++;
} else {
add[j][addlen[j]++] = line{y, x};
rem[i][remlen[i]++] = line{y, x};
}
}
}
void compress() {
sort(p, p + n, comp);
for(int i = 0; i <= n; i++) {
query[i] = {{inf, inf}, inf};
}
for(int i = 0; i < n; i++) {
if(i == 0 || ccw(pii(0, 0), p[i].f, p[i - 1].f))
k++;
arr[p[i].s] = k;
query[k] = min(query[k], p[i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0; i < n; i++) {
pii tmp;
cin >> tmp.f >> tmp.s;
p[i].f = tmp;
p[i].s = i;
org[i] = p[i].f;
}
compress();
for(int i = 0; i < n - 1; i++)
add_edge(arr[i], arr[i + 1], i, i + 1, true);
add_edge(arr[n - 1], arr[0], n - 1, 0, true);
for(int i = 1; i <= k; i++) {
add[i] = new line[addlen[i]];
rem[i] = new line[remlen[i]];
addlen[i] = 0;
remlen[i] = 0;
}
for(int i = 0; i < n - 1; i++)
add_edge(arr[i], arr[i + 1], i, i + 1, false);
add_edge(arr[n - 1], arr[0], n - 1, 0, false);
sweep();
cout << ans.size() << endl;
sort(ans.begin(), ans.end());
for(int i : ans) {
cout << i + 1 << " ";
}
cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
616 KB |
Output is correct |
| 3 |
Correct |
4 ms |
928 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1004 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1800 KB |
Output is correct |
| 6 |
Correct |
16 ms |
1916 KB |
Output is correct |
| 7 |
Correct |
36 ms |
3156 KB |
Output is correct |
| 8 |
Correct |
9 ms |
3156 KB |
Output is correct |
| 9 |
Correct |
11 ms |
3156 KB |
Output is correct |
| 10 |
Correct |
14 ms |
3156 KB |
Output is correct |
| 11 |
Correct |
19 ms |
3156 KB |
Output is correct |
| 12 |
Correct |
21 ms |
3216 KB |
Output is correct |
| 13 |
Correct |
54 ms |
4576 KB |
Output is correct |
| 14 |
Correct |
34 ms |
5516 KB |
Output is correct |
| 15 |
Correct |
49 ms |
6796 KB |
Output is correct |
| 16 |
Execution timed out |
127 ms |
12904 KB |
Time limit exceeded |
| 17 |
Execution timed out |
197 ms |
13872 KB |
Time limit exceeded |
| 18 |
Execution timed out |
234 ms |
25164 KB |
Time limit exceeded |
| 19 |
Execution timed out |
173 ms |
25164 KB |
Time limit exceeded |
| 20 |
Execution timed out |
425 ms |
27148 KB |
Time limit exceeded |
