#include <bits/stdc++.h>
using namespace std;
const int Qmax = 10005, Nmax = 2005;
const double PI = acos(-1);
typedef long long ll;
int Lines, Rows, L, C, N, Q, p, i, j, r, ans;
bool good[Qmax];
struct point
{
int x, y;
point operator - (const point &other) const
{
return {x - other.x, y - other.y};
}
};
vector<point> A;
point a[Nmax], S, q[Qmax];
bool cmp(point a, point b)
{
double p1 = atan2(a.y, a.x), p2 = atan2(b.y, b.x);
if(p1 < 0) p1 += 2*PI;
if(p2 < 0) p2 += 2*PI;
return p1 < p2;
}
bool ord(point a, point b, point c)
{
a = a-c, b = b-c;
return (ll)a.x * b.y > (ll)a.y * b.x;
}
int Find(point P)
{
int st = 0, dr = A.size() - 1, mid;
while(st <= dr)
{
mid = (st+dr) / 2;
if(cmp(P, A[mid])) dr = mid-1;
else st = mid+1;
}
return st % A.size();
}
int main()
{
// freopen("input", "r", stdin);
// freopen("output", "w", stdout);
cin.sync_with_stdio(false);
cin >> Lines >> Rows >> S.x >> S.y;
cin >> Q;
for(i=1; i<=Q; ++i) cin >> q[i].x >> q[i].y, good[i] = 1;
cin >> N;
for(i=1; i<=N; ++i) cin >> a[i].x >> a[i].y;
ans = Q;
for(i=1; i<=N; ++i)
{
A.clear();
for(j=1; j<=N; ++j)
if(i != j) A.push_back(a[i] - a[j]);
sort(A.begin(), A.end(), cmp);
p = Find(S - a[i]);
if(!p) r = A.size() - 1;
else r = p - 1;
for(j=1; j<=Q; ++j)
if(good[j] && !ord(A[r], q[j] - a[i], A[p])) good[j] = 0, --ans;
}
cout << ans << '\n';
for(i=1; i<=Q; ++i)
if(good[i]) cout << i << ' ';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
248 KB |
Output isn't correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Incorrect |
2 ms |
568 KB |
Output isn't correct |
4 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
5 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
6 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
7 |
Incorrect |
6 ms |
736 KB |
Output isn't correct |
8 |
Incorrect |
5 ms |
736 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
736 KB |
Output is correct |
2 |
Incorrect |
4 ms |
736 KB |
Output isn't correct |
3 |
Incorrect |
6 ms |
736 KB |
Output isn't correct |
4 |
Correct |
9 ms |
736 KB |
Output is correct |
5 |
Correct |
9 ms |
736 KB |
Output is correct |
6 |
Correct |
19 ms |
748 KB |
Output is correct |
7 |
Incorrect |
2 ms |
748 KB |
Output isn't correct |
8 |
Correct |
3 ms |
748 KB |
Output is correct |
9 |
Incorrect |
6 ms |
748 KB |
Output isn't correct |
10 |
Incorrect |
46 ms |
748 KB |
Output isn't correct |
11 |
Incorrect |
27 ms |
764 KB |
Output isn't correct |
12 |
Correct |
44 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3039 ms |
768 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |