#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Vector {
int x;
int y;
};
ll f(Vector a, Vector b) {
return (a.x - b.x) * (ll) (a.y + b.y);
}
ll f(Vector a, Vector b, Vector c) {
return f(a, b) + f(b, c) + f(c, a);
}
Vector operator + (Vector a, Vector b) {
return { a.x + b.x, a.y + b.y };
}
Vector operator - (Vector a, Vector b) {
return { a.x - b.x, a.y - b.y };
}
Vector operator * (Vector a, ll b) {
return { a.x * b, a.y * b };
}
Vector operator * (ll b, Vector a) {
return { a.x * b, a.y * b };
}
Vector readVector() {
int x, y;
cin >> x >> y;
return { x, y };
}
const int N = 2000 + 7;
const int C = 10000 + 7;
int w, h;
int n, c;
int cnt_good[C];
Vector camps[C];
Vector trees[N];
Vector myself;
int get_type(Vector a) {
if (a.x == w) return 0;
if (a.y == h) return 1;
if (a.x == 0) return 2;
if (a.y == 0) return 3;
}
bool cmpOnRect(int i, int j) {
Vector a = camps[i];
Vector b = camps[j];
int type_a = get_type(a);
int type_b = get_type(b);
if (type_a != type_b) return type_a < type_b;
int type = type_a;
if (type == 0) {
return a.y < b.y;
}
if (type == 1) {
return a.x > b.x;
}
if (type == 2) {
return a.y > b.y;
}
if (type == 3) {
return a.x < b.x;
}
}
int get_cadran(Vector a) {
if (a.x >= 0) {
if (a.y > 0) {
return 2;
} else {
return 1;
}
} else {
if (a.y < 0) {
return 0;
} else {
return 3;
}
}
}
bool cmp_Vector(Vector a, Vector b) {
int cadran_a = get_cadran(a);
int cadran_b = get_cadran(b);
if (cadran_a != cadran_b) {
return cadran_a < cadran_b;
}
return (f({0, 0}, a, b) > 0);
}
bool cmp2(pair<Vector, int> a, pair<Vector, int> b) {
return cmp_Vector(a.first, b.first);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> w >> h;
myself = readVector();
vector<int> inds;
cin >> c;
for (int i = 1; i <= c; i++) {
camps[i] = readVector();
inds.push_back(i);
}
sort(inds.begin(), inds.end(), cmpOnRect);
cin >> n;
for (int i = 1; i <= n; i++) {
trees[i] = readVector();
}
for (int tid = 1; tid <= n; tid++) {
Vector origin = trees[tid];
vector<pair<Vector, int>> events;
for (int i = 1; i <= n; i++) {
if (i == tid) continue;
Vector delta = trees[i] - origin;
events.push_back({ {-delta.x,-delta.y}, -1 });
}
events.push_back({ myself - origin, 0 });
auto cop_events = events;
int start = 0;
for (int P = 1; P < c; P++) {
int i = inds[P];
if (cmp_Vector(camps[i] - origin, camps[start] - origin)) {
start = P;
}
}
vector<pair<Vector, int>> cps;
for (int l = 0; l < c; l++) {
int i = inds[(start + l) % c];
cps.push_back({ camps[i] - origin, i });
}
sort(cop_events.begin(), cop_events.end(), cmp2);
vector<pair<Vector, int>> so;
int p1 = 0, p2 = 0;
while (p1 < (int)cps.size() && p2 < (int)cop_events.size()) {
if (cmp2(cps[p1], cop_events[p2])) {
so.push_back(cps[p1++]);
}
else {
so.push_back(cop_events[p2++]);
}
}
while (p1 < (int)cps.size()) {
so.push_back(cps[p1++]);
}
while (p2 < (int)cop_events.size()) {
so.push_back(cop_events[p2++]);
}
events = so;
int p0 = 0;
while (events[p0].second != 0) p0++;
int l = p0, r = p0, sz = (int)events.size();
while (events[(l + sz - 1) % sz].second != -1) l = (l + sz - 1) % sz;
while (events[(r + 1) % sz].second != -1) r = (r + 1) % sz;
for (int j = l; j != (r + 1) % sz; j = (j + 1) % sz) {
if (events[j].second > 0) {
cnt_good[events[j].second]++;
}
}
}
vector<int> sol;
for (int i = 1; i <= c; i++) {
if (cnt_good[i] == n) {
sol.push_back(i);
}
}
cout << (int)sol.size() << "\n";
for (auto& i : sol) {
cout << i << " ";
}
cout << "\n";
}
Compilation message
fangorn.cpp: In function 'Vector operator*(Vector, ll)':
fangorn.cpp:29:16: warning: narrowing conversion of '(((ll)a.Vector::x) * b)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
29 | return { a.x * b, a.y * b };
| ~~~~^~~
fangorn.cpp:29:25: warning: narrowing conversion of '(((ll)a.Vector::y) * b)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
29 | return { a.x * b, a.y * b };
| ~~~~^~~
fangorn.cpp: In function 'Vector operator*(ll, Vector)':
fangorn.cpp:34:16: warning: narrowing conversion of '(((ll)a.Vector::x) * b)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
34 | return { a.x * b, a.y * b };
| ~~~~^~~
fangorn.cpp:34:25: warning: narrowing conversion of '(((ll)a.Vector::y) * b)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
34 | return { a.x * b, a.y * b };
| ~~~~^~~
fangorn.cpp: In function 'int get_type(Vector)':
fangorn.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
60 | }
| ^
fangorn.cpp: In function 'bool cmpOnRect(int, int)':
fangorn.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
83 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
3 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 10 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 11 |
Correct |
4 ms |
340 KB |
Output is correct |
| 12 |
Correct |
4 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
634 ms |
580 KB |
Output is correct |
| 2 |
Incorrect |
1269 ms |
976 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
