#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
struct Vector {
ll x;
ll 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;
const ld eps=1e-14;
bool cmp(pair<Vector, int> a, pair<Vector, int> b) {
return atan2((ld)a.first.y, (ld)a.first.x) - atan2((ld)b.first.y, (ld)b.first.x)<eps;
}
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;
}
}
ld get_f(pair<ld, ld> a, pair<ld, ld> b) {
return (a.first - b.first) * (a.second + b.second);
}
ld get_f(pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> c) {
return get_f(a, b) + get_f(b, c) + get_f(c, a);
}
int get_cadran(pair<ld, ld> a) {
if (a.first >= 0) {
if (a.second >= 0) {
return 0;
} else {
return 3;
}
} else {
if (a.second <= 0) {
return 2;
} else {
return 1;
}
}
}
int tr_cadran(int c) {
return (c + 2) % 4;
}
bool cmp_pld(pair<ld, ld> a, pair<ld, ld> b) {
int cadran_a = get_cadran(a);
int cadran_b = get_cadran(b);
cadran_a = tr_cadran(cadran_a);
cadran_b = tr_cadran(cadran_b);
if (cadran_a != cadran_b) {
return cadran_a < cadran_b;
}
return (get_f(pair<ld, ld> (0, 0), a, b) > 0);
}
int get_cadran(Vector a) {
if (a.x >= 0) {
if (a.y > 0) {
return 0;
} else {
return 3;
}
} else {
if (a.y < 0) {
return 2;
} else {
return 1;
}
}
}
bool cmp_Vector(Vector a, Vector b) {
int cadran_a = get_cadran(a);
int cadran_b = get_cadran(b);
cadran_a = tr_cadran(cadran_a);
cadran_b = tr_cadran(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);
/// freopen ("input.txt", "r", stdin);
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;
ld minAng = (ld)1e18;
int start = -1;
for (int P = 0; P < c; P++) {
int i = inds[P];
Vector vec = camps[i] - origin;
ld ang = atan2(vec.y, vec.x);
if (ang < minAng) {
minAng = ang;
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 (cmp(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 'int get_type(Vector)':
fangorn.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
67 | }
| ^
fangorn.cpp: In function 'bool cmpOnRect(int, int)':
fangorn.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
90 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 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 |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
4 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
9 ms |
340 KB |
Output is correct |
| 11 |
Correct |
8 ms |
340 KB |
Output is correct |
| 12 |
Correct |
8 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
175 ms |
340 KB |
Output is correct |
| 5 |
Correct |
39 ms |
340 KB |
Output is correct |
| 6 |
Correct |
824 ms |
524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1129 ms |
956 KB |
Output is correct |
| 2 |
Correct |
2531 ms |
1996 KB |
Output is correct |
| 3 |
Correct |
2641 ms |
1900 KB |
Output is correct |
| 4 |
Correct |
2600 ms |
1836 KB |
Output is correct |
