#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
pair<pii,int> a[MAXN];
pii b[MAXN];
int n;
bool ans[MAXN], vis[MAXN];
int sgn(pii x, pii y, pii z)
{
ll ret = 1ll*(ll)(y.fi - x.fi) * (z.se - x.se) - 1ll*(ll)(z.fi - x.fi) * (y.se - x.se);
if (ret == 0)
return 0;
return ret > 0 ? 1 : -1;
}
bool dist(pii lhs, pii rhs)
{
return lhs.fi+lhs.se < rhs.fi+rhs.se;
}
int nx(int i, int d)
{
i += d;
if (i > n)
i = 1;
if (i < 1)
i = n;
return i;
}
int pr(int i, int d)
{
i -= d;
if (i > n)
i = 1;
if (i < 1)
i = n;
return i;
}
int d = 1;
struct cmp
{
bool operator()(pair<pii,int> lh, pair<pii,int> rh)
{
if (lh == rh)
return false;
pii lhs = lh.fi, rhs = rh.fi;
if (sgn({0,0},lhs,rhs)>=0)
return (sgn(lhs,b[nx(lh.se,d)],rhs)<=0);
else
return (sgn(rhs,b[nx(rh.se,d)],lhs)>0);
}
};
set<pair<pii,int>, cmp> q;
vi p;
int main()
{
clock_t t = clock();
ni(n);
int first = 1, last = 1;
for (int i = 1; i <= n; i++)
{
ni(a[i].fi.fi), ni(a[i].fi.se);
a[i].se = i;
b[i] = a[i].fi;
if (i == 1)
continue;
int o1 = sgn({0,0},b[first],b[i]);
if (o1<0||o1==0&&b[i].fi<b[first].fi)
first = i;
o1 = sgn({0,0},b[last],b[i]);
if (o1>0||o1==0&&b[i].fi<b[last].fi)
last = i;
}
int x1 = first + 1; if (x1 > n) x1 = 1;
int x2 = first - 1; if (x2 == 0) x2 = n;
if (sgn(b[first], b[x1], b[x2]) < 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;
for (int i = first; i != nx(last, d); i = nx(i, d))
p.pb(i);
sort(p.begin(), p.end(), [](int l, int r) -> bool
{
pii lhs = b[l], rhs = b[r];
int o = sgn({0, 0}, lhs, rhs);
if (o == 0)
return dist(lhs, rhs);
return o > 0 ? true : false;
});
ans[first] = 1;
q.insert({b[first],first});
vis[first] = 1;
for (int i = 1; i < p.size(); i++)
{
int a1 = p[i];
int a2 = pr(p[i], d);
if (vis[a2])
{
if ((*q.begin()).se == a2 && sgn({0,0},b[a1],b[p[i-1]]) != 0)
ans[a1] = 1, m++;
q.erase(mp(b[a2], a2));
vis[a2] = false;
}
a2 = nx(p[i], d);
if (sgn({0,0}, b[a1], b[a2]) > 0)
{
vis[a1] = 1;
q.insert(mp(b[a1],a1));
if ((*q.begin()).se == a1 && sgn({0,0},b[a1],b[p[i-1]]) != 0 && !ans[a1])
ans[a1] = 1, m++;
}
}
if (!ans[last])
ans[last] = 1, m++;
pri(m);
for (int i = 1; i <= n; i++)
if (ans[i])
printf("%d ", i);
enl;
cout<<clock()-t<<"\n";
return 0;
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:98:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (o1<0||o1==0&&b[i].fi<b[first].fi)
^
circuit.cpp:101:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (o1>0||o1==0&&b[i].fi<b[last].fi)
^
circuit.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < p.size(); i++)
~~^~~~~~~~~~
circuit.cpp:7: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:88:5: note: in expansion of macro 'ni'
ni(n);
^~
circuit.cpp:92:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ni(a[i].fi.fi), ni(a[i].fi.se);
^
circuit.cpp:92:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
380 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
584 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
668 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
668 KB |
Output isn't correct |
| 5 |
Incorrect |
9 ms |
996 KB |
Output isn't correct |
| 6 |
Incorrect |
14 ms |
1328 KB |
Output isn't correct |
| 7 |
Incorrect |
18 ms |
1840 KB |
Output isn't correct |
| 8 |
Incorrect |
8 ms |
1840 KB |
Output isn't correct |
| 9 |
Incorrect |
8 ms |
1840 KB |
Output isn't correct |
| 10 |
Incorrect |
11 ms |
1952 KB |
Output isn't correct |
| 11 |
Incorrect |
11 ms |
1976 KB |
Output isn't correct |
| 12 |
Incorrect |
17 ms |
2512 KB |
Output isn't correct |
| 13 |
Incorrect |
27 ms |
3276 KB |
Output isn't correct |
| 14 |
Incorrect |
22 ms |
3796 KB |
Output isn't correct |
| 15 |
Incorrect |
29 ms |
4732 KB |
Output isn't correct |
| 16 |
Incorrect |
58 ms |
7232 KB |
Output isn't correct |
| 17 |
Incorrect |
75 ms |
8804 KB |
Output isn't correct |
| 18 |
Execution timed out |
113 ms |
13552 KB |
Time limit exceeded |
| 19 |
Execution timed out |
122 ms |
15992 KB |
Time limit exceeded |
| 20 |
Execution timed out |
208 ms |
19460 KB |
Time limit exceeded |
