#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define C complex<ll>
#define X real()
#define Y imag()
ll w,h,n,c;
C g;
C camp[10005];
C tree[10005];
bool can[15];
int sign(ll x) {
if(x > 0) {
return 1;
} else if(x == 0) {
return 0;
} else {
return -1;
}
}
ll cross(C a, C b) { //-1 bal, 0 egyenes, 1 jobb A hoz képest a B
return sign(((a*conj(b)).Y));
}
bool isbadv[10005];
int leftest[10005];
int rightest[10005];
int leftof[10005];
int rightof[10005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll gx,gy;
cin >> w >> h >> gx >> gy >> c;
g = {gx,gy};
for(int i = 0; i < c; i++) {
ll x,y;
cin >> x >> y;
camp[i] = {x,y};
}
cin >> n;
for(int i = 0; i < n; i++) {
ll x,y;
cin >> x >> y;
tree[i] = {x,y};
}
for(int i = 0; i < n; i++) {
bool bad = false;
int fix = (i == 0 ? 1 : 0);
for(int j = 0; j < n; j++) {
if(j == i || j == fix) {
continue;
}
if(cross(tree[fix]-tree[i],tree[j]-tree[i]) > 0) {
fix = j;
}
}
for(int j = 0; j < n; j++) {
if(j == i || j == fix) {
continue;
}
if(cross(tree[fix]-tree[i],tree[j]-tree[i]) > 0) {
bad = true;
}
}
if(bad) {
int left1 = -1;
for(int x = 0; x < n; x++) {
if(x == i) {
continue;
}
if(cross(tree[i]-g,tree[x]-tree[i]) < 0) {
if(left1 == -1 || cross(tree[x]-tree[i],tree[left1]-tree[i]) < 0) {
left1 = x;
}
}
}
leftof[i] = left1;
int right1 = -1;
for(int x = 0; x < n; x++) {
if(x == i) {
continue;
}
if(cross(tree[i]-g,tree[x]-tree[i]) > 0) {
if(right1 == -1 || cross(tree[x]-tree[i],tree[right1]-tree[i]) > 0) {
right1 = x;
}
}
}
rightof[i] = right1;
isbadv[i] = true;
} else {
leftest[i] = fix;
}
}
for(int i = 0; i < n; i++) {
if(isbadv[i]) {
continue;
}
int fix = (i == 0 ? 1 : 0);
for(int j = 0; j < n; j++) {
if(j == i || j == fix) {
continue;
}
if(cross(tree[fix]-tree[i],tree[j]-tree[i]) < 0) {
fix = j;
}
}
rightest[i] = fix;
//cout << i << " " << leftest[i] << " " << rightest[i] << "a\n";
}
vector<int> pr;
for(int i = 0; i < c; i++) {
bool good = true;
/* for(int x = 0; x < n; x++) {
for(int y = x+1; y < n; y++) {
if(isbad[x][y]) {
if(cross(tree[y]-tree[x],g-tree[x]) == -cross(tree[y]-tree[x],camp[i]-tree[x])) {
good = false;
}
}
}
}
// cout << good << "\n";
if(!good) {
continue;
}*/
for(int a2 = 0; a2 < n && good; a2++) {
if(!isbadv[a2]) {
int b1 = a2;
int a1 = leftest[a2];
int b2 = rightest[a2];
if(b2 == a1 || b2 == a2) {
continue;
}
if(cross(tree[a2]-tree[a1],camp[i]-tree[a1]) != -cross(tree[a2]-tree[a1],g-tree[a1]) && cross(tree[b2]-tree[b1],camp[i]-tree[b1]) != -cross(tree[b2]-tree[b1],g-tree[b1])) {
continue;
}
if(cross(tree[a2]-tree[a1],tree[b2]-tree[a1]) == -cross(tree[a2]-tree[a1],camp[i]-tree[a1]) && cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) == -cross(tree[b2]-tree[b1],camp[i]-tree[b1])) {
good = false;
// cout << a1 << " " << b1 << " " << b2 << endl;
}
if(cross(tree[a2]-tree[a1],tree[b2]-tree[a1]) == -cross(tree[a2]-tree[a1],g-tree[a1]) && cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) == -cross(tree[b2]-tree[b1],g-tree[b1])) {
good = false;
// cout << a1 << " " << b1 << " " << b2 << endl;
}
} else {
int left1 = leftof[a2];
int right1 = rightof[a2];
if(cross(tree[a2]-camp[i],tree[left1]-tree[a2]) > 0 || cross(tree[a2]-camp[i],tree[right1]-tree[a2]) < 0) {
good = false;
}
// if(i == 2) {
// cout << left1 << " " << left2 << endl;
//}
}
}
if(good) {
pr.push_back(i+1);
}
}
cout << pr.size() << "\n";
for(int el : pr) {
cout << el << " ";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
416 KB |
Output is correct |
| 4 |
Correct |
3 ms |
492 KB |
Output is correct |
| 5 |
Correct |
4 ms |
536 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Correct |
2 ms |
612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
620 KB |
Output is correct |
| 4 |
Correct |
3 ms |
620 KB |
Output is correct |
| 5 |
Correct |
2 ms |
620 KB |
Output is correct |
| 6 |
Correct |
3 ms |
620 KB |
Output is correct |
| 7 |
Correct |
2 ms |
620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
620 KB |
Output is correct |
| 9 |
Correct |
2 ms |
620 KB |
Output is correct |
| 10 |
Correct |
4 ms |
716 KB |
Output is correct |
| 11 |
Correct |
4 ms |
716 KB |
Output is correct |
| 12 |
Correct |
3 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
716 KB |
Output is correct |
| 2 |
Correct |
3 ms |
716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
716 KB |
Output is correct |
| 4 |
Correct |
26 ms |
716 KB |
Output is correct |
| 5 |
Correct |
8 ms |
716 KB |
Output is correct |
| 6 |
Correct |
68 ms |
808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
808 KB |
Output is correct |
| 2 |
Correct |
317 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
112 ms |
1132 KB |
Output is correct |
| 4 |
Correct |
282 ms |
1308 KB |
Output is correct |
