#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (2005)
#define MAXC (10005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
ll ccw(pll a, pll b, pll c) {
return (a.first*b.second + b.first*c.second + c.first*a.second)
- (a.second*b.first + b.second*c.first + c.second*a.first);
}
vector<int> G[2][MAXN];
vector<int> Ans;
int CX[MAXC], CY[MAXC];
int TX[MAXN], TY[MAXN];
int N, C, W, H, GX, GY;
int main() {
scanf("%d%d%d%d", &W, &H, &GX, &GY);
scanf("%d", &C); for(int i = 1; i <= C; i++) scanf("%d%d", &CX[i], &CY[i]);
scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d%d", &TX[i], &TY[i]);
for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) {
if(i == j) continue;
const ll dt = ccw({GX, GY}, {TX[i], TY[i]}, {TX[j], TY[j]});
G[dt < 0][i].pb(j);
}
for(int i = 1; i <= N; i++) for(int j = 0; j < 2; j++)
sort(allv(G[j][i]), [&](const int& a, const int& b) -> bool {
return 0 < ccw({TX[i], TY[i]}, {TX[a], TY[a]}, {TX[b], TY[b]});
});
for(int i = 1; i <= C; i++) {
bool flag = false;
for(int j = 1; j <= N; j++) {
if(G[1][j].empty()) {
if(sz(G[0][j]) < 2) continue;
const int a = G[0][j][0];
const int b = G[0][j].back();
if(0 < ccw({TX[a], TY[a]}, {TX[j], TY[j]}, {CX[i], CY[i]}) &&
ccw({TX[b], TY[b]}, {TX[j], TY[j]}, {CX[i], CY[i]}) < 0) {
flag = true; break;
}
} else if(G[0][j].empty()) {
if(sz(G[1][j]) < 2) continue;
const int a = G[1][j][0];
const int b = G[1][j].back();
if(0 < ccw({TX[a], TY[a]}, {TX[j], TY[j]}, {CX[i], CY[i]}) &&
ccw({TX[b], TY[b]}, {TX[j], TY[j]}, {CX[i], CY[i]}) < 0) {
flag = true; break;
}
} else {
const int a = G[1][j][0];
const int b = G[0][j].back();
if(ccw({TX[a], TY[a]}, {TX[j], TY[j]}, {TX[b], TY[b]}) < 0) {
if(0 < ccw({TX[a], TY[a]}, {TX[j], TY[j]}, {CX[i], CY[i]}) ||
ccw({TX[b], TY[b]}, {TX[j], TY[j]}, {CX[i], CY[i]}) < 0) {
flag = true; break;
}
} else {
if(ccw({TX[a], TY[a]}, {TX[j], TY[j]}, {CX[i], CY[i]}) < 0 &&
0 < ccw({TX[b], TY[b]}, {TX[j], TY[j]}, {CX[i], CY[i]})) {
flag = true; break;
}
}
}
}
if(flag) continue;
Ans.pb(i);
}
printf("%d\n", sz(Ans));
if(!Ans.empty()) { for(int v : Ans) printf("%d ", v); puts(""); }
return 0;
}
Compilation message
fangorn.cpp: In function 'int main()':
fangorn.cpp:51:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &W, &H, &GX, &GY);
^
fangorn.cpp:52:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &C); for(int i = 1; i <= C; i++) scanf("%d%d", &CX[i], &CY[i]);
^
fangorn.cpp:52:76: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &C); for(int i = 1; i <= C; i++) scanf("%d%d", &CX[i], &CY[i]);
^
fangorn.cpp:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d%d", &TX[i], &TY[i]);
^
fangorn.cpp:53:76: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d%d", &TX[i], &TY[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
2212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 8 |
Correct |
0 ms |
2212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
2344 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 8 |
Correct |
0 ms |
2212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2476 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2476 KB |
Output is correct |
| 12 |
Correct |
3 ms |
2476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
486 ms |
23708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
