#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct Vector {
ll x;
ll y;
/**Vector() : x(0), y(0) {
}
Vector(ll x, ll y) : x(x), y(y) {
}*/
};
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;
bool cmpByAngle(Vector a, Vector b) {
return atan2((ld)a.y, (ld)a.x) < atan2((ld)b.y, (ld)b.x);
}
bool cmp(pair<Vector, int> a, pair<Vector, int> b) {
return cmpByAngle(a.first, b.first);
}
int get_type(Vector a) {
assert(a.x == 0 || a.x == w || a.y == 0 || a.y == h);
if (a.x == w) return 0;
if (a.y == h) return 1;
if (a.x == 0) return 2;
if (a.y == 0) return 3;
assert(0);
}
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) {
assert(a.y != b.y);
return a.y < b.y;
}
if (type == 1) {
assert(a.x != b.x);
return a.x > b.x;
}
if (type == 2) {
assert(a.y != b.y);
return a.y > b.y;
}
if (type == 3) {
assert(a.x != b.x);
return a.x < b.x;
}
assert(0);
}
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++) {
/// tid=3;
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;
/// trees[i] - origin = delta
/// trees[i] = origin + delta
events.push_back({ {-delta.x,-delta.y}, -1 });
}
events.push_back({ myself - origin, 0 });
auto cop_events = events;
assert((int)inds.size() == c);
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;
}
}
assert(start != -1);
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(), cmp);
sort(cps.begin(), cps.end(), cmp);
vector<pair<Vector, int>> so;
/// so = mrg(cps, cop_events)
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;
/**cout<<"\t\t\t\t";
for (int i=1;i<=c;i++) {
cout<<cnt_good[i]<<" ";
}
cout<<"\n";
events=so;**/
int cox = 0;
/*cout<<"0 0 O\n";
for (auto &it : events) {
cox++;
cout<<it.first.x<<" "<<it.first.y<<" P";
if (it.second==-1) {
cout<<"x";
}else{
cout<<it.second;
}
cout<<"\n";
}*/
int p0 = 0;
while (events[p0].second != 0) p0++;
assert(p0 < (int)events.size());
assert(events[p0].second == 0);
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 (auto &j : events) {
cout<<j.second<<" ";
}
cout<<" -------> ";
cout<<" = "<<l<<" and "<<r<<"\n";
*/
for (int j = l; j != (r + 1) % sz; j = (j + 1) % sz) {
assert(events[j].second >= 0);
if (events[j].second > 0) {
assert(1 <= events[j].second && events[j].second <= c);
cnt_good[events[j].second]++;
}
}
///return 0;
}
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 main()':
fangorn.cpp:188:9: warning: unused variable 'cox' [-Wunused-variable]
188 | int cox = 0;
| ^~~
| # |
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 |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
7 ms |
340 KB |
Output is correct |
| 8 |
Correct |
7 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
212 KB |
Output is correct |
| 3 |
Correct |
6 ms |
340 KB |
Output is correct |
| 4 |
Correct |
8 ms |
340 KB |
Output is correct |
| 5 |
Correct |
8 ms |
340 KB |
Output is correct |
| 6 |
Correct |
24 ms |
360 KB |
Output is correct |
| 7 |
Correct |
0 ms |
244 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
6 ms |
340 KB |
Output is correct |
| 10 |
Correct |
52 ms |
344 KB |
Output is correct |
| 11 |
Correct |
67 ms |
340 KB |
Output is correct |
| 12 |
Correct |
69 ms |
360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1834 ms |
444 KB |
Output is correct |
| 5 |
Correct |
424 ms |
392 KB |
Output is correct |
| 6 |
Execution timed out |
3065 ms |
732 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3068 ms |
1152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
