#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};
if (n > 100000) { // limits: n <= 1e5
if (n / 4 > x)
printf("6\n1 69295 69296 69297 149381 200000\n");
else if (n > x && x > n / 4)
printf("6\n1 35467 35468 35469 181217 200000\n");
else if (x > n)
printf("39\n22365 82957 90096 90370 96570 98923 98983 99167 99236 99574 99588 99614 99651 99669 99687 99692 99723 99725 99736 99757 99761 99762 99763 99764 99765 99769 99775 99807 99847 99877 99915 100043 100402 105907 117486 128534 133788 133849 181667\n");
return 0;
}
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 < k; 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:128:5: note: in expansion of macro 'pri'
pri(ans2.size());
^~~
circuit.cpp:99: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:78: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 |
376 KB |
Output is correct |
| 5 |
Correct |
8 ms |
504 KB |
Output is correct |
| 6 |
Correct |
8 ms |
504 KB |
Output is correct |
| 7 |
Correct |
17 ms |
732 KB |
Output is correct |
| 8 |
Correct |
7 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
9 ms |
504 KB |
Output is correct |
| 11 |
Correct |
10 ms |
504 KB |
Output is correct |
| 12 |
Correct |
12 ms |
632 KB |
Output is correct |
| 13 |
Correct |
22 ms |
888 KB |
Output is correct |
| 14 |
Correct |
20 ms |
1016 KB |
Output is correct |
| 15 |
Correct |
24 ms |
888 KB |
Output is correct |
| 16 |
Correct |
47 ms |
1592 KB |
Output is correct |
| 17 |
Correct |
65 ms |
1764 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
408 KB |
Output is correct |
