#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Point {
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
Point operator - (const Point &p) const {
return Point(x - p.x, y - p.y);
}
bool operator < (const Point &p) const {
return x < p.x || (x == p.x && y < p.y);
}
bool operator == (const Point &p) const {
return x == p.x && y == p.y;
}
ll cross(const Point &p) const {
return (ll) x * p.y - (ll) y * p.x;
}
};
bool ccw(Point p, Point q) {
return p.cross(q) > 0;
}
Point org = Point();
void read(Point &p) {
cin >> p.x >> p.y;
}
const int N = 1010;
const int C = 10100;
int w, h;
int c, n;
Point g;
Point cm[C];
Point tr[N];
bool fail[N];
bool cmp(Point p, Point q) {
bool fp = org < p;
bool fq = org < q;
if (fp ^ fq) {
return fp;
} else {
return ccw(p, q);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin >> w >> h;
read(g);
cin >> c;
for (int i = 1; i <= c; ++i) {
read(cm[i]);
}
cin >> n;
for (int i = 1; i <= n; ++i) {
read(tr[i]);
}
for (int i = 1; i <= n; ++i) {
vector<Point> ps;
Point ng = g - tr[i];
ps.push_back(ng);
for (int j = 1; j <= n; ++j) if (j != i) {
ps.push_back(tr[i] - tr[j]);
}
// cout << "At " << i << "\n";
sort(ps.begin(), ps.end(), cmp);
/*
for (auto p : ps) {
cout << p.x << ' ' << p.y << "\n";
}
*/
Point bl, br;
for (int j = 0; j < n; ++j) {
if (ng == ps[j]) {
bl = ps[(j + n - 1) % n];
br = ps[(j + 1) % n];
break;
}
}
// cout << "bl :" << bl.x << ' ' << bl.y << "\n";
// cout << "br :" << br.x << ' ' << br.y << "\n";
for (int j = 1; j <= c; ++j) {
Point cm = ::cm[j] - tr[i];
if (ccw(bl, br)) {
fail[j] |= (!(ccw(bl, cm) & ccw(cm, br)));
} else {
fail[j] |= (ccw(br, cm) & ccw(cm, bl));
}
}
}
int ans = 0;
for (int i = 1; i <= c; ++i) ans += !fail[i];
cout << ans << '\n';
for (int i = 1; i <= c; ++i) if (!fail[i]) {
cout << i << ' ';
}
}
# |
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 |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
# |
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 |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
452 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
88 ms |
480 KB |
Output is correct |
5 |
Correct |
19 ms |
480 KB |
Output is correct |
6 |
Incorrect |
377 ms |
504 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
398 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |