#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;
struct pt {
int x, y;
int p;
pt() {x = 0, y = 0, p = 0;}
pt(int x, int y) {
this->x = x;
this->y = y;
if (y == 0) {
if (x > 0) p = 1;
else p = 3;
} else {
if (y > 0) p = 2;
else p = 4;
}
}
};
bool cmp(pt a, pt b) {
if (a.p != b.p) return a.p < b.p;
return (llint)b.x * a.y < (llint)a.x * b.y;
}
int w, h;
int xg, yg;
int n, c;
int xc[maxn], yc[maxn];
int x[maxn], y[maxn];
vector< int > uphul, downhul;
bool sol[maxn];
int main() {
scanf("%d%d%d%d", &w, &h, &xg, &yg);
scanf("%d", &c);
for (int i = 0; i < c; i++)
scanf("%d%d", xc+i, yc+i);
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", x+i, y+i);
for (int i = 0; i < c; i++) sol[i] = true;
for (int i = 0; i < n; i++) {
//printf("fixing: %d (%d %d)\n", i + 1, x[i], y[i]);
vector< pt > v;
for (int j = 0; j < n; j++) {
if (i == j) continue;
pt tren(x[i] - x[j], y[i] - y[j]);
v.push_back(tren);
}
pt ac(xg - x[i], yg - y[i]);
v.push_back(ac);
sort(v.begin(), v.end(), cmp);
//printf("target: (%d %d)\n", ac.x, ac.y);
//printf("debug: "); for (int j = 0; j < v.size(); j++) printf("(%d %d) ", v[j].x, v[j].y);
//printf("\n");
for (int j = 0; j < v.size(); j++) {
if (!(v[j].x == ac.x && v[j].y == ac.y)) continue;
pt a = v[(j - 1 + v.size()) % v.size()];
if (j == 0) a.p -= 4;
pt b = v[(j + 1) % v.size()];
if (j + 1 == v.size()) b.p += 4;
for (int k = 0; k < c; k++) {
if (!sol[k]) continue;
pt tren(xc[k] - x[i], yc[k] - y[i]);
//printf("trying %d: (%d %d)\n", k, tren.x, tren.y);
bool flag = false;
if (cmp(a, tren) && cmp(tren, b)) flag = true;
tren.p += 4;
if (cmp(a, tren) && cmp(tren, b)) flag = true;
tren.p -= 8;
if (cmp(a, tren) && cmp(tren, b)) flag = true;
//printf("eliminated %d\n", k);
if (!flag) sol[k] = false;
}
}
}
int kol = 0;
for (int i = 0; i < c; i++) kol += sol[i];
printf("%d\n", kol);
for (int i = 0; i < c; i++)
if (sol[i]) printf("%d ", i + 1);
printf("\n");
return 0;
}
Compilation message
fangorn.cpp: In function 'int main()':
fangorn.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
fangorn.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | if (j + 1 == v.size()) b.p += 4;
| ~~~~~~^~~~~~~~~~~
fangorn.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d%d%d%d", &w, &h, &xg, &yg);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d", &c);
| ~~~~~^~~~~~~~~~
fangorn.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d%d", xc+i, yc+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
fangorn.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
fangorn.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d%d", x+i, y+i);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
308 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
216 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
4 ms |
204 KB |
Output is correct |
| 11 |
Correct |
4 ms |
204 KB |
Output is correct |
| 12 |
Correct |
4 ms |
312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
114 ms |
332 KB |
Output is correct |
| 5 |
Correct |
24 ms |
344 KB |
Output is correct |
| 6 |
Correct |
483 ms |
392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
499 ms |
424 KB |
Output is correct |
| 2 |
Correct |
564 ms |
612 KB |
Output is correct |
| 3 |
Correct |
521 ms |
612 KB |
Output is correct |
| 4 |
Correct |
437 ms |
588 KB |
Output is correct |
