正文
[LOJ6437]PKUSC
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
旋转多边形是没有前途的，我们考虑旋转敌人，那么答案就是所有人的可行区间长度之和除以$2\pi$
首先对每个敌人找到那些旋转后会落到多边形上的角度，实际上就是圆和一些线段求交，解方程即可，注意判一下落在多边形端点上的情况
把角度排序，每相邻两个角度构成一个区间，在区间内随便取一个角度，把敌人旋转这个角度，判断敌人是否在多边形内，如果是那么整个区间都是可行的
旋转直接套公式：$\left[\matrix{x'\\y'}\right]=\left[\matrix{\cos\theta&-\sin\theta\\\sin\theta&\cos\theta}\right]\left[\matrix{x\\y}\right]$
判断点是否在多边形内：考虑站在这个点，按顺序望向多边形的每个顶点，如果转了$2\pi$弧度就在多边形里，如果转了$0$弧度就在多边形外
注意精度，算夹角时绝对不要用asin或acos，对判别式判断大小不能用eps
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef double du;
const du eps=1e-9,pi2=2*M_PI;
bool equ(du a,du b){return fabs(a-b)<eps;}
bool lt(du a,du b){return a-b<-eps;}
bool inr(du a,du b,du c){
if(a>c)swap(a,c);
return lt(a,b)&<(b,c);
}
struct point{
du x,y;
point(du a=0,du b=0){x=a;y=b;}
};
point operator-(point a,point b){return point(a.x-b.x,a.y-b.y);}
du dot(point a,point b){return a.x*b.x+a.y*b.y;}
du cr(point a,point b){return a.x*b.y-a.y*b.x;}
du len(point a){return sqrt(a.x*a.x+a.y*a.y);}
du dif(point a,point b){
if(equ(len(a)*len(b),0))return 0;
if(equ(cr(a,b),0))return lt(0,dot(a,b))?0:-M_PI;
du f=atan2(b.y,b.x)-atan2(a.y,a.x);
if(lt(cr(a,b),0)){
if(lt(0,f))f-=pi2;
}else if(lt(f,0))
f+=pi2;
return f;
}
void eq2(du a,du b,du c,du&d,du&x1,du&x2){
d=b*b-4*a*c;
if(d>=0){
x1=(-b+sqrt(d))/(2*a);
x2=(-b-sqrt(d))/(2*a);
}
}
du ang[1010];
int M;
void chk(point u,point a,point b){
du x1,x2,r;
r=len(u);
if(equ(r,len(a)))ang[++M]=dif(u,a);
if(equ(a.x,b.x)){
if(lt(r,a.x))return;
x1=sqrt(r*r-a.x*a.x);
x2=-x1;
if(inr(a.y,x1,b.y))ang[++M]=dif(u,point(a.x,x1));
if(inr(a.y,x2,b.y))ang[++M]=dif(u,point(a.x,x2));
}else{
du d,K,B;
K=(b.y-a.y)/(b.x-a.x);
B=a.y-K*a.x;
eq2(K*K+1,2*K*B,B*B-r*r,d,x1,x2);
if(d<0)return;
if(inr(a.x,x1,b.x))ang[++M]=dif(u,point(x1,K*x1+B));
if(inr(a.x,x2,b.x))ang[++M]=dif(u,point(x2,K*x2+B));
}
}
point e[210],p[510];
int n,m;
#define gao(b,c) if(equ(cr(u-b,u-c),0))return 0;\
t+=dif(b-u,c-u);
bool inside(point u){
du t=0;
int i;
for(i=1;i<m;i++){
gao(p[i],p[i+1])
}
gao(p[m],p[1])
return equ(t,pi2);
}
point rot(point a,du ang){
return point(a.x*cos(ang)-a.y*sin(ang),a.x*sin(ang)+a.y*cos(ang));
}
#define chk2(a,b,c) if(inside(rot(a,(b+c)*.5)))ans+=(c-b)/pi2;
int main(){
int i,j;
du ans;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%lf%lf",&e[i].x,&e[i].y);
for(i=1;i<=m;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
ans=0;
for(i=1;i<=n;i++){
M=0;
for(j=1;j<m;j++){
chk(e[i],p[j],p[j+1]);
}
chk(e[i],p[m],p[1]);
if(M<2){
if(inside(e[i]))ans+=1;
}else{
sort(ang+1,ang+M+1);
for(j=1;j<M;j++){
chk2(e[i],ang[j],ang[j+1])
}
chk2(e[i],ang[M],ang[1]+pi2)
}
}
printf("%.5lf",ans);
}
