#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Pont {
ll x, y;
int id;
void olvas(int i) {
id = i;
cin>>x>>y;
}
bool operator== (Pont masik) {
return id == masik.id;
}
};
Pont vec(Pont a, Pont b) {
b.x -= a.x;
b.y -= a.y;
return b;
}
int sgn(ll exp) {
if(0LL < exp) return 1;
if(exp < 0LL) return -1;
return 0;
}
int Irany(Pont o, Pont a, Pont b) {
a = vec(o,a);
b = vec(o,b);
ll cp = a.x * b.y - a.y * b.x;
return sgn(cp);
}
bool Kozte(Pont a, Pont b, Pont c) {
a = vec(b,a);
c = vec(b,c);
if(sgn(a.x) == -sgn(c.x) && sgn(a.x) != 0) return true;
if(sgn(a.y) == -sgn(c.y) && sgn(a.y) != 0) return true;
return false;
}
Pont sp;
bool kisebb(Pont p, Pont q) {
int dir = Irany(sp,p,q);
if(dir != 0) {
return dir == 1;
}
return Kozte(sp,p,q);
}
struct Szak{
Pont a, b;
Szak() { }
Szak(Pont aa, Pont bb) {
a = aa;
b = bb;
}
const bool operator< (Szak M) const {
if(a.id == M.a.id && b.id == M.b.id) return false;
if(a.id == M.b.id && b.id == M.a.id) return false;
if(M.a == a) {
return Irany(M.a,M.b,b) == 1;
}
if(M.b == b) {
return Irany(M.b,M.a,a) == -1;
}
if(M.a == b) {
return a.id < M.b.id;
}
if(M.b == a) {
return b.id < M.a.id;
}
if(Irany(a,b,M.a) == 0 && Irany(a,b,M.b) == 0 && Irany(a, b, sp) == 0) {
if(Kozte(sp,a,M.a) && Kozte(sp,b,M.a)) return true;
if(Kozte(sp,M.a,a) && Kozte(sp,M.b,a)) return false;
}
if(Irany(M.a, M.b, a) == Irany(M.a, M.b, b)) return Irany(M.a, M.b, a) == 1;
if(Irany(a,b,M.a) == Irany(a,b,M.b)) return Irany(a, b, M.a) == -1;
return false;
}
};
const int maxn = 200005;
int n;
Pont t[maxn];
Pont v[maxn];
bool sol[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(int i=1;i<=n;i++) {
t[i].olvas(i);
v[i] = t[i];
}
t[n+1] = t[1];
t[0] = t[n];
sort(v+1,v+n+1,kisebb);
set<Szak> H;
for(int i=1;i<=n;i++) {
int idj = v[i].id;
if(Irany(sp,t[idj],t[idj+1]) >= 0) {
Szak uj(t[idj],t[idj+1]);
H.insert(uj);
}
if(Irany(sp,t[idj],t[idj-1]) >= 0) {
Szak uj(t[idj],t[idj-1]);
H.insert(uj);
}
Szak k = *H.begin();
int dir = Irany(sp,k.a,k.b);
if(dir == 0 && k.a.id == idj && Kozte(sp,k.a,k.b)) sol[idj] = true;
if(dir == 0 && k.b.id == idj && Kozte(sp,k.b,k.a)) sol[idj] = true;
if(dir != 0 && k.a.id == idj) sol[idj] = true;
if(dir != 0 && k.b.id == idj) sol[idj] = true;
if(Irany(sp,t[idj],t[idj+1]) <= 0) {
Szak re(t[idj+1],t[idj]);
H.erase(re);
}
if(Irany(sp,t[idj],t[idj-1]) <= 0) {
Szak re(t[idj-1],t[idj]);
H.erase(re);
}
}
int db = 0;
for(int i=1;i<=n;i++) {
if(sol[i]) db++;
}
cout<<db<<endl;
for(int i=1;i<=n;i++) {
if(sol[i]) {
cout<<i<<" ";
}
}
cout<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
640 KB |
Output is correct |
| 4 |
Correct |
5 ms |
640 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 7 |
Correct |
21 ms |
2048 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1024 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1280 KB |
Output is correct |
| 10 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 11 |
Correct |
15 ms |
1280 KB |
Output is correct |
| 12 |
Correct |
14 ms |
1536 KB |
Output is correct |
| 13 |
Correct |
34 ms |
2816 KB |
Output is correct |
| 14 |
Correct |
29 ms |
2688 KB |
Output is correct |
| 15 |
Correct |
35 ms |
3328 KB |
Output is correct |
| 16 |
Correct |
68 ms |
6400 KB |
Output is correct |
| 17 |
Execution timed out |
127 ms |
8732 KB |
Time limit exceeded |
| 18 |
Execution timed out |
140 ms |
12408 KB |
Time limit exceeded |
| 19 |
Execution timed out |
136 ms |
12352 KB |
Time limit exceeded |
| 20 |
Execution timed out |
315 ms |
16492 KB |
Time limit exceeded |
