This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Fangorn"
int n, c;
class point{
public:
ll x, y;
void input(){
read(x);
read(y);
}
point operator -(){
point res;
res.x=-x;
res.y=-y;
return res;
}
bool ccw(point A, point B){
A.x-=x;
A.y-=y;
B.x-=x;
B.y-=y;
return (A.x*B.y-B.x*A.y)>0;
}
bool cw(point A, point B){
A.x-=x;
A.y-=y;
B.x-=x;
B.y-=y;
return (A.x*B.y-B.x*A.y)<0;
}
bool ccw(point A, point B, point C){
if(ccw(A, C)==ccw(B, C)) return ccw(A, B);
else return ccw(B, C);
}
bool cw(point A, point B, point C){
if(cw(A, C)==cw(B, C)) return cw(A, B);
else return cw(B, C);
}
} s, p[10001], t[2001];
bool good[10001];
ll w, h;
int main(){
#ifdef Aria
if(fopen(taskname".in", "r"))
freopen(taskname".in", "r", stdin);
#endif // Aria
read(w);
read(h);
s.input();
read(c);
FOR(i, 1, c) p[i].input();
read(n);
FOR(i, 1, n) t[i].input();
FOR(i, 1, c) good[i]=1;
FOR(i, 1, n){
point bccw, bcw;
bool first=1;
FOR(j, 1, n) if(j!=i){
point R=p[j];
R.x=t[i].x*2-t[j].x;
R.y=t[i].y*2-t[j].y;
if(first){
first=0;
bccw=bcw=R;
}
else{
if(t[i].ccw(bccw, R, s)) bccw=R;
if(t[i].cw(bcw, R, s)) bcw=R;
}
}
FOR(j, 1, c) if(good[j]) good[j]=t[i].ccw(bccw, p[j], bcw);
// bug(i);
// cerr<<bccw.x<<' '<<bccw.y<<' '<<bcw.x<<' '<<bcw.y<<'\n';
}
int ans=0;
FOR(i, 1, c) ans+=good[i];
writeln(ans);
FOR(i, 1, c) if(good[i]) write(i), putchar(' ');
putchar('\n');
}
Compilation message (stderr)
fangorn.cpp: In function 'int main()':
fangorn.cpp:36:12: warning: '*((void*)& bccw +8)' may be used uninitialized in this function [-Wmaybe-uninitialized]
A.y-=y;
~~~^~~
fangorn.cpp:73:15: note: '*((void*)& bccw +8)' was declared here
point bccw, bcw;
^~~~
fangorn.cpp:35:12: warning: 'bccw' may be used uninitialized in this function [-Wmaybe-uninitialized]
A.x-=x;
~~~^~~
fangorn.cpp:73:15: note: 'bccw' was declared here
point bccw, bcw;
^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |