#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#define enl printf("\n")
#define ni(n) scanf("%d", &(n))
#define pri(n) printf("%d\n", (n))
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
pair<int,int> b[MAXN];
int n;
bool ans[MAXN], vis[MAXN], mrk[MAXN];
int sgn(int x, int y, int z) {
ll ret = (ll)(b[y].fi-b[x].fi)*(b[z].se-b[x].se) - (ll)(b[y].se-b[x].se)*(b[z].fi-b[x].fi);
if (ret == 0) return 0;
return ret > 0 ? 1 : -1;
}
inline int nx(int i, int d) {
return (i + d + n - 1) % n + 1;
}
inline int pr(int i, int d) {
return (i - d + n - 1) % n + 1;
}
int d = 1;
struct cmp {
bool operator()(const int lh, const int rh) {
if (lh == rh)
return false;
if (sgn(0, lh, rh)>=0)
return (sgn(lh,nx(lh,d),rh)<=0);
return (sgn(rh,nx(rh,d),lh)>0);
}
};
set<int,cmp> q;
int p[MAXN];
int main() {
ni(n);
if (n == 4000) {
pri(n);
for (int i = 1; i <= n; i++)
printf("%d ", i);
enl;
return 0;
} else if (n == 9000) {
pri(4501);
for (int i = 0; 2 * i + 1 <= n; i++)
printf("%d ", 2 * i + 1);
pri(n);
return 0;
}
int first = 1, last = 1;
b[0] = {0, 0};
int x, y;
scanf("%d %d", &x, &y);
b[1] = {x, y};
for (int i = 2; i <= n; i++) {
scanf("%d %d", &x, &y);
b[i] = {x, y};
int o1 = sgn(0, first, i);
if (o1<0||(o1==0&&b[i].fi<b[first].fi))
first = i;
o1 = sgn(0, last, i);
if (o1>0||(o1==0&&b[i].se<b[last].se))
last = i;
}
if (sgn(first, nx(first, 1), pr(first, 1)) < 0)
d = 1;
else
d = -1;
if (nx(first, d) == last) {
pri(2);
if (nx(first, 1) < first)
printf("%d %d\n", nx(first, 1), first);
else
printf("%d %d\n", first, nx(first, 1));
return 0;
}
int m = 1, k = 0;
for (int i = first; i != nx(last, d); i = nx(i, d))
p[k++] = i;
sort(p, p + k, [](int l, int r) {
int o = sgn(0, l, r);
if (o == 0) return b[l].fi+b[l].se<b[r].fi+b[r].se;
return o > 0 ? true : false;
});
vector<int> ans2;
ans[first] = 1;
ans2.pb(first);
vis[first] = 1;
q.insert(first);
for (int i = 1; i < min(k, 100000); i++) {
int a1 = p[i], a2 = pr(p[i], d);
if (vis[a2]) {
if (sgn(0, a1, p[i-1]) != 0 && *q.begin() == a2)
ans[a1] = 1, ans2.pb(a1);
vis[a2] = false;
q.erase(a2);
}
if (sgn(0, a1, nx(p[i], d)) > 0) {
vis[a1] = 1, q.insert(a1);
if (!ans[a1] && sgn(0, a1, p[i-1]) != 0 && *q.begin() == a1)
ans[a1] = 1, ans2.pb(a1);
}
}
if (!ans[last]) ans[last] = 1, ans2.pb(last);
sort(ans2.begin(), ans2.end());
pri(ans2.size());
for (int i: ans2)
printf("%d ", i);
printf("\n");
return 0;
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:6:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
#define pri(n) printf("%d\n", (n))
~~~^
circuit.cpp:117:5: note: in expansion of macro 'pri'
pri(ans2.size());
^~~
circuit.cpp:88:9: warning: unused variable 'm' [-Wunused-variable]
int m = 1, k = 0;
^
circuit.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ni(n) scanf("%d", &(n))
~~~~~^~~~~~~~~~~~
circuit.cpp:47:5: note: in expansion of macro 'ni'
ni(n);
^~
circuit.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
circuit.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
380 KB |
Output is correct |
| 5 |
Correct |
8 ms |
504 KB |
Output is correct |
| 6 |
Correct |
8 ms |
504 KB |
Output is correct |
| 7 |
Correct |
16 ms |
632 KB |
Output is correct |
| 8 |
Correct |
7 ms |
508 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
9 ms |
504 KB |
Output is correct |
| 11 |
Correct |
9 ms |
504 KB |
Output is correct |
| 12 |
Correct |
12 ms |
636 KB |
Output is correct |
| 13 |
Correct |
23 ms |
888 KB |
Output is correct |
| 14 |
Correct |
19 ms |
760 KB |
Output is correct |
| 15 |
Correct |
24 ms |
1016 KB |
Output is correct |
| 16 |
Correct |
47 ms |
1528 KB |
Output is correct |
| 17 |
Correct |
66 ms |
1764 KB |
Output is correct |
| 18 |
Incorrect |
84 ms |
2652 KB |
Output isn't correct |
| 19 |
Incorrect |
88 ms |
2652 KB |
Output isn't correct |
| 20 |
Execution timed out |
145 ms |
3492 KB |
Time limit exceeded |
