#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 << 17;
struct line {
pii a, b;
};
int n, k;
pair<pii, int> p[maxn];
pii org[maxn];
int arr[maxn];
vector<line> add[maxn];
vector<line> rem[maxn];
vector<pair<pii, int> > query[maxn];
vector<int> ans;
ll ccw(pii a, pii b, 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(pii(0, 0), a.f, b.f);
if(c == 0)
return a.s < b.s;
return c > 0;
}
bool operator==(line x, line y) {
return x.a == y.a && x.b == y.b;
}
bool operator<(line x, line y) {
if(x == y)
return false;
// if(x.a == y.a)
// return x.b < y.b;
// if(x.a == y.b)
// return x.b < y.a;
// if(x.b == y.a)
// return x.a < y.b;
// if(x.b == y.b)
// return x.a < y.a;
bool ret = false;
// ll sum = ccw(pii(0, 0), y.a, y.b)
// + ccw(pii(0, 0), y.b, x.b)
// + ccw(pii(0, 0), x.b, x.a)
// + ccw(pii(0, 0), x.a, y.a);
ll sum = ccw(x.a, y.a, x.b) + ccw(x.b, y.a, y.b);
if(sum == 0) {
if(x.a.s == y.a.s)
return x.a.f < y.a.f;
return x.a.f < y.a.f;
}
ret = sum > 0;
// ll xa, xb, ya, yb;
// xa = ccw(x.a, x.b, y.a);
// xb = ccw(x.a, x.b, y.b);
// ya = ccw(y.a, y.b, x.a);
// yb = ccw(y.a, y.b, x.b);
// if(!xa && !xb && !ya && !yb) {
// if(x.a.s == y.a.s)
// return x.a.f < y.a.f;
// return x.a.f < y.a.f;
// }
// // cout << "values: " << xa << " " << xb << " " << ya << " " << yb << endl;
// if((xa > 0) == (xb > 0) || !xa || !xb) {
// if(!xa)
// ret = xb < 0;
// else
// ret = xa < 0;
// } else if ((ya > 0) == (yb > 0) || !ya || !yb) {
// if(!ya)
// ret = yb > 0;
// else
// ret = ya > 0;
// } else {
// // cout << x.a.f << "," << x.a.s << "-" << x.b.f << "," << x.b.s << " " << y.a.f << "," << y.a.s << "-" << y.b.f << "," << y.b.s << endl;
// assert(false);
// }
// cout << ret << " " << ": " << x.a.f << "," << x.a.s << "-" << x.b.f << "," << x.b.s << " " << y.a.f << "," << y.a.s << "-" << y.b.f << "," << y.b.s << endl;
// cout << endl;
return ret;
}
void sweep() {
multiset<line> st;
for(int t = 1; t <= k; t++) {
for(const line &i : add[t]) {
st.insert(i);
}
// if(t == 102) {
// for(auto i : st)
// cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " ";
// cout << endl;
// }
// assert(!st.empty());
line f = *st.begin();
sort(query[t].begin(), query[t].end());
for(const pair<pii, int> &i : query[t]) {
// assert(!st.empty());
if(ccw(f.a, f.b, i.f) == 0) {
ans.push_back(i.s);
}
break;
}
// cout << "trebam izbrisat: ";
// for(const line &i : rem[t]) {
// cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " ";
// }
// cout << endl;
for(const line &i : rem[t]) {
// cout<<(i < i)<<endl;
auto it = st.find(i);
// assert(it != st.end());
// if(it != st.end())
st.erase(it);
}
// cout << "success ";
// cout << t << ": ";
// for(line i : st) {
// cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " ";
// }
// cout << endl;
}
}
void add_edge(int i, int j, int x, int y) {
if(i < j) {
add[i].push_back(line{org[x], org[y]});
rem[j].push_back(line{org[x], org[y]});
} else {
add[j].push_back(line{org[y], org[x]});
rem[i].push_back(line{org[y], org[x]});
}
}
void compress() {
sort(p, p + n, comp);
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].push_back(p[i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// while(true) {
// int a, b, c, d;
// cin >> a >> b >> c >> d;
// line x{pii(a, b), pii(c, d)};
// int aa, bb, cc, dd;
// cin >> aa >> bb >> cc >> dd;
// line y{pii(aa, bb), pii(cc, dd)};
// cout << (x < y) << endl;
// }
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; i++) {
// cout << arr[i] << " ";
// }
// cout << endl;
for(int i = 0; i < n - 1; i++)
add_edge(arr[i], arr[i + 1], i, i + 1);
add_edge(arr[n - 1], arr[0], n - 1, 0);
// for(int i = 1; i <= n; i++) {
// cout << i << ": ";
// for(line j : add[i]) {
// cout << j.a.f << "," << j.a.s << "-" << j.b.f << "," << j.b.s << " ";
// }
// cout << endl;
// }
// cout << endl;
// cout << arr[21] << " " << arr[22] << endl;
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 |
10 ms |
9596 KB |
Output is correct |
| 2 |
Correct |
12 ms |
9700 KB |
Output is correct |
| 3 |
Correct |
17 ms |
10160 KB |
Output is correct |
| 4 |
Correct |
14 ms |
10236 KB |
Output is correct |
| 5 |
Correct |
34 ms |
11020 KB |
Output is correct |
| 6 |
Correct |
24 ms |
11048 KB |
Output is correct |
| 7 |
Correct |
51 ms |
12176 KB |
Output is correct |
| 8 |
Correct |
20 ms |
12176 KB |
Output is correct |
| 9 |
Correct |
29 ms |
12176 KB |
Output is correct |
| 10 |
Correct |
30 ms |
12176 KB |
Output is correct |
| 11 |
Correct |
24 ms |
12176 KB |
Output is correct |
| 12 |
Correct |
32 ms |
12176 KB |
Output is correct |
| 13 |
Correct |
68 ms |
13580 KB |
Output is correct |
| 14 |
Correct |
75 ms |
14220 KB |
Output is correct |
| 15 |
Correct |
91 ms |
15372 KB |
Output is correct |
| 16 |
Execution timed out |
102 ms |
20976 KB |
Time limit exceeded |
| 17 |
Execution timed out |
198 ms |
22032 KB |
Time limit exceeded |
| 18 |
Runtime error |
59 ms |
27292 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
75 ms |
29548 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
66 ms |
29548 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
