题意转化为:
判断每个点所在的圆有多长的弧度角位于多边形内部。
然后就很暴力了。
每个点P,直接找到多边形和这个圆的所有交点,按照距离P的角度排序。
找交点,直接联立二元二次方程组。。。。
需要判断一段弧是否在多边形内部。
向量随机旋转角度,判断点是否在多边形内部即可。
如果该点在多边形边上,返回-1,重新旋转。
由于double,所以不会出现射线在多边形边上情况。
注意:
(0,0)要特判是否在多边形内部。+eps判断
#include<bits/stdc++.h>
#define reg register int
using namespace std;
// using namespace Modulo;
namespace Miracle{
const int N=;
const double eps=1e-;
const double inf=1e8;
const double Pi=acos(-);
int n,m;
struct po{
double x,y;
po(){}
po(double xx,double yy){
x=xx;y=yy;
}
double friend operator *(po a,po b){
return a.x*b.y-a.y*b.x;
}
double dis(){
return sqrt(x*x+y*y);
}
po friend operator -(po a,po b){
return po(a.x-b.x,a.y-b.y);
}
double deg(){
return atan2(y,x);
}
po xuan(double d){
double nd=deg()-d;
double len=dis();
return po(len*cos(nd),len*sin(nd));
}
void op(){
cout<<"("<<x<<","<<y<<")"<<endl;
}
}p[N],q[N];
struct node{
po P;
double c;
node(){}
node(double cc,po PP){
c=cc;P=PP;
}
bool friend operator <(node a,node b){
return a.c<b.c;
}
}cur[N];
struct line{
double k,b;
po A,B;
double f(double x){
if(k<inf) return k*x+b;
return A.y;
}
}l[N];
bool on(po c,line L){//c on L?
if(c.x+eps>=L.A.x&&c.x<=L.B.x+eps){
if(L.k==inf) {
if(c.y+eps>=L.A.y&&c.y<=L.B.y+eps) return ;
}
else{double ny=L.f(c.x);
if(fabs(ny-c.y)<eps) return ;}
}
return ;
}
bool jiao(line a,line b){
double c1=(a.A-b.A)*(a.A-b.B),c2=(a.B-b.A)*(a.B-b.B);
double c3=(b.A-a.A)*(b.A-a.B),c4=(b.B-a.A)*(b.B-a.B);
if(c1*c2<=&&c3*c4<=) return true;
return false;
}
int in(po a){
int cnt=;
line now;
now.k=;now.b=a.y;
now.A=a;now.B=po(inf,a.y);
for(reg i=;i<=m;++i){
if(on(a,l[i])) return -;
if(jiao(now,l[i])) ++cnt;
}
if(cnt&) return ;
return ;
}
double cha(double d1,double d2){
if(d1>=&&d2<=){
return d1-d2;
}else if(d1>=&&d2>=){
if(d1>d2) return d1-d2;
return *Pi-(d2-d1);
}else if(d1<=&&d2>=){
return *Pi-(d2-d1);
}else if(d1<=&&d2<=){
if(d1>d2) return (d1-d2);
return *Pi-(d2-d1);
}
return ;
}
double sui(){
return (double)rand()/(RAND_MAX);
}
double calc(po a){
int cnt=;
double r=a.dis();
if(r==){
a.y+=eps;
if(in(a)==) return *Pi;
else return ;
}
for(reg i=;i<=m;++i){
if(l[i].k<inf){
double A=(+l[i].k*l[i].k);
double B=*l[i].k*l[i].b;
double C=l[i].b*l[i].b-r*r;
double deta=B*B-*A*C;
if(deta>=){
double x1=(-B+sqrt(deta))/(*A),x2=(-B-sqrt(deta))/(*A);
po now=po(x1,l[i].f(x1));
if(on(now,l[i])) {
cur[++cnt]=node(cha(a.deg(),now.deg()),now);
}
now=po(x2,l[i].f(x2));
if(on(now,l[i])){
cur[++cnt]=node(cha(a.deg(),now.deg()),now);
}
}
}else{
double lp=r*r-l[i].A.x*l[i].A.x;
double X=l[i].A.x;
if(lp>){
double Y=sqrt(lp);
po now=po(X,Y);
if(on(now,l[i])) {
cur[++cnt]=node(cha(a.deg(),now.deg()),now);
}
Y=-sqrt(lp);
now=po(X,Y);
if(on(now,l[i])){
cur[++cnt]=node(cha(a.deg(),now.deg()),now);
}
}
}
} cur[++cnt]=node(,a);
cur[++cnt]=node(*Pi,a);
sort(cur+,cur+cnt+);
double ret=;
for(reg i=;i<=cnt;++i){
double d=cur[i].c-cur[i-].c;
if(d<0.0000001) continue;
po now=cur[i-].P;
int tmp=-;
while(tmp==-){
double z=d*sui();
now=cur[i-].P.xuan(z);
tmp=in(now);
}
if(tmp==){
ret+=d;
}
}
return ret; }
int main(){
srand((unsigned long long)new char);
cin>>n>>m;
for(reg i=;i<=n;++i){
double x,y;
scanf("%lf%lf",&x,&y);
q[i]=po(x,y);
}
for(reg i=;i<=m;++i){
double x,y;
scanf("%lf%lf",&x,&y);
p[i]=po(x,y);
}
for(reg i=;i<=m;++i){
int nxt=(i==m)?:i+;
l[i].A=p[i];l[i].B=p[nxt];
if(p[i].x>p[nxt].x||(p[i].x==p[nxt].x&&p[i].y>p[nxt].y)) swap(l[i].A,l[i].B); if(p[i].x==p[nxt].x){
l[i].k=inf;
}else{
l[i].k=(p[nxt].y-p[i].y)/(p[nxt].x-p[i].x);
l[i].b=((p[nxt].x*p[i].y)-(p[i].x*p[nxt].y))/(p[nxt].x-p[i].x);
}
} double ans=0.0;
for(reg i=;i<=n;++i){
ans+=calc(q[i]);
}
ans=ans/(*Pi);
printf("%.5lf",ans);
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
*/