#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;
for (int i=1;i<=c;i++) {
events.push_back({camps[i]-origin, i});
}
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++]);
}
sort(events.begin(), events.end(),cmp);
if (0) {
for (auto &it : so) cout<<it.second<<" "; cout<<"\n";
for (auto &it : events) cout<<it.second<<" "; cout<<"\n\n";
for (int i=0;i<(int)so.size();i++) {
cout<<so[i].first.x<<" "<<so[i].first.y<<" P"<<i<<"\n";
}
for (int i=0;i<(int)events.size();i++) {
cout<<events[i].first.x<<" "<<events[i].first.y<<" P"<<i<<"\n";
}
exit(0);
}
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:185:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
185 | for (auto &it : so) cout<<it.second<<" "; cout<<"\n";
| ^~~
fangorn.cpp:185:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
185 | for (auto &it : so) cout<<it.second<<" "; cout<<"\n";
| ^~~~
fangorn.cpp:186:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
186 | for (auto &it : events) cout<<it.second<<" "; cout<<"\n\n";
| ^~~
fangorn.cpp:186:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
186 | for (auto &it : events) cout<<it.second<<" "; cout<<"\n\n";
| ^~~~
fangorn.cpp:203:9: warning: unused variable 'cox' [-Wunused-variable]
203 | 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 |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
12 ms |
340 KB |
Output is correct |
| 8 |
Correct |
13 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
344 KB |
Output is correct |
| 3 |
Correct |
12 ms |
344 KB |
Output is correct |
| 4 |
Correct |
16 ms |
340 KB |
Output is correct |
| 5 |
Correct |
19 ms |
340 KB |
Output is correct |
| 6 |
Correct |
51 ms |
328 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
268 KB |
Output is correct |
| 9 |
Correct |
11 ms |
340 KB |
Output is correct |
| 10 |
Correct |
98 ms |
340 KB |
Output is correct |
| 11 |
Correct |
117 ms |
340 KB |
Output is correct |
| 12 |
Correct |
123 ms |
360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
4 ms |
212 KB |
Output is correct |
| 3 |
Correct |
5 ms |
324 KB |
Output is correct |
| 4 |
Execution timed out |
3077 ms |
468 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3078 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
