799G - Cut the pie - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=20005;
const double pi=acos(-1),eps=1e-14;
inline int dcmp(double x){return fabs(x)<eps?0:(x>0?1:-1);}
struct poi{
double x,y;
inline void in(){scanf("%lf%lf",&x,&y);}
}a[N],aa[N],z;
struct vec{
double x,y;
inline double operator*(const vec&rhs){
return x*rhs.y-y*rhs.x;
}
inline vec operator*(const double&rhs){
return(vec){x*rhs,y*rhs};
}
};
vec operator-(const poi&a,const poi&b){return(vec){a.x-b.x,a.y-b.y};}
poi operator+(const poi&a,const vec&b){return(poi){a.x+b.x,a.y+b.y};}
int n,q,i,l,r,m,bi,ei,be,en;
double sum[N],l1,r1,m1;
inline double geta(int l,int r){
return sum[r]-sum[l]-(a[r]-a[1])*(a[l]-a[1])/2;
}
inline double calc(double x){
int p1,p2;
vec y=(vec){-cos(x),-sin(x)};
l=bi;r=ei;
for(;l<r;){
m=(l+r+1)>>1;
if(dcmp((a[m]-z)*y)<=0)l=m;
else r=m-1;
}
p1=l;y=(vec){-y.x,-y.y};
for(l=ei,r=bi+n;l<r;){
m=(l+r+1)>>1;
if(dcmp((a[m]-z)*y)<=0)l=m;
else r=m-1;
}
p2=l;
double ss=p2+1-n>0?geta(p2+1-n,p1):sum[n]-geta(p1,p2+1);
poi q1,q2;
double k;
k=fabs(((a[p1+1]-z)*y)/((a[p1]-z)*y));
k=1/(1+k);
q1=a[p1]+(a[p1+1]-a[p1])*k;
k=fabs(((a[p2+1]-z)*y)/((a[p2]-z)*y));
k=1/(1+k);
q2=a[p2]+(a[p2+1]-a[p2])*k;
ss+=((a[p2+1]-a[p1])*(q2-a[p1])+(q1-q2)*(a[p1]-q2))/2;
return dcmp(ss-(sum[n]-ss));
}
int main(){
scanf("%d%d",&n,&q);
for(i=be=en=1;i<=n;++i){
aa[i].in();
if(aa[i].y>aa[be].y||(aa[i].y==aa[be].y&&aa[i].x<aa[be].x))be=i;
if(aa[i].y<aa[en].y||(aa[i].y==aa[en].y&&aa[i].x>aa[en].x))en=i;
}
en-=be-1;if(en<=0)en+=n;
for(i=be;i<=n;++i)a[i-be+1]=aa[i];
for(;i<n+be;++i)a[i-be+1]=aa[i-n];
for(i=n+1;i<=2*n;++i)a[i]=a[i-n];
for(i=3;i<=n;++i)sum[i]=sum[i-1]+(a[i]-a[1])*(a[i-1]-a[1])/2;
while(q--){
z.in();
for(l=1+(a[1].y==a[2].y),r=en-1;l<r;){
m=(l+r+1)>>1;
if(a[m].y>=z.y)l=m;
else r=m-1;
}
bi=l;
for(l=en+(a[en].y==a[en+1].y),r=n;l<r;){
m=(l+r+1)>>1;
if(z.y>=a[m].y)l=m;
else r=m-1;
}
ei=l;
int p=calc(0);
if(p==0){puts("0");continue;}
l1=0,r1=pi;
for(int i=0;i<60&&l1<r1;++i){
m1=(l1+r1)/2;
if(calc(m1)==p)l1=m1;
else r1=m1;
}
printf("%.17lf\n",l1);
}
return 0;
}