带劲的计算几何【这一定是我WC之前开的最后一道计几！！！
每个点画个圆然后看一下交点 然后判断是多边形内还是多边形外
这个就是取圆上中点然后射线法
eps我1e-8才过 不知道为啥有的人说只能开1e-3
写了三天带劲= =
还有注意long double！附了一组数据~
//Love and Freedom.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 20021225
#define ll long long
#define eps 1e-8
#define mxn 510
#define db long double
using namespace std;
const db pi = acosl(-1.0);
struct poi
{
db x,y;
poi(){}
poi(db _x,db _y){x=_x,y=_y;}
};
typedef poi vec;
bool operator ==(vec a,vec b){return a.x==b.x&&a.y==b.y;}
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator *(vec a,db b){return vec(a.x*b,a.y*b);}
db cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
db value(vec a,vec b){return a.x*b.x+a.y*b.y;}
db len(vec a){return a.x*a.x+a.y*a.y;}
db ang(vec a){return atan2(a.y,a.x);}
struct line
{
poi p; vec v; db ang;
line(){}
line(poi _p,poi _v)
{
p=_p; v=_v;
ang = atan2(v.y,v.x);
}
}li[mxn];
db cir[mxn]; int cnt,n,m;
poi mid[mxn];
db section(line a,line b)
{
db k = cross(a.v+a.p-b.p,a.p-b.p)/(cross(a.v+a.p-b.p,b.v)+cross(b.v,a.p-b.p));
return k;
}
void get(line a,db r)
{
db c = - r*r + len(a.p);
db aa = len(a.v);
db b = 2.0*(a.v.x*a.p.x+a.v.y*a.p.y);
db delta = b*b - 4.0 * aa * c;
if(delta < 0) return ;
delta = sqrt(delta);
db k1 = (-b + delta)/(2.0*aa);
if(abs(delta)<eps)
{
poi tmp = a.p+a.v*k1;
if(k1>-eps && k1-1.0<eps) cir[++cnt] =atan2(tmp.y,tmp.x);
return;
}
db k2 = (-b-delta)/(2.0*aa);
poi tmp = a.p+a.v*k1;
if(k1>-eps && k1-1.0<eps) cir[++cnt] = atan2(tmp.y,tmp.x);
tmp = a.p+a.v*k2;
if(k2>-eps && k2-1.0<eps) cir[++cnt] = atan2(tmp.y,tmp.x);
}
void put(poi a)
{
printf("p===%lf %lf
",a.x,a.y);
}
void putl(line a)
{
printf("ls--------------
");
put(a.p); put(a.v); printf("%lf
",a.ang);
printf("le--------------
");
}
bool between(line a,poi b)
{
int tmp=0;
if(a.v.x <= 0.0)
{
if(b.x <= a.p.x && b.x >= a.p.x+a.v.x) tmp++;
}
else
{
if(b.x >= a.p.x && b.x <= a.p.x+a.v.x) tmp++;
}
if(a.v.y <= 0.0)
{
if(b.y <= a.p.y && b.y >= a.p.y+a.v.y) tmp++;
}
else
{
if(b.y >= a.p.y && b.y <= a.p.y+a.v.y) tmp++;
}
return tmp==2;
}
bool check(poi x)
{
for(int i=1;i<=m;i++)
if(between(li[i],x) && abs(cross(x-li[i].p,li[i].v))<eps)
return 0;
int cer = 0;
line tmp = line(x,poi(2794406.11,-2564800.0132));
for(int i=1;i<=m;i++)
{
db w = section(tmp,li[i]);
db ww = section(li[i],tmp);
if( ww>1.0 || ww<0.0 || w>1.0 || w<0.0)
continue;
cer++;
}
if(cer&1) return 1;
return 0;
}
bool cmp(poi a,poi b)
{
return ang(a) < ang(b) || (abs(ang(a)-ang(b))<eps&& cross(a,b)>eps);
}
bool same(poi a,poi b)
{
return abs(a.x-b.x)<eps && abs(a.y-b.y) <eps;
}
poi enemy[mxn],stk[mxn];
db makecircle(int id,db r)
{
cnt = 0; db ans = 0.0;
for(int i=1;i<=m;i++)
get(li[i],r);
if(!cnt)
{
if(check(enemy[id])) return 2*pi;
return 0.0;
}
sort(cir+1,cir+cnt+1);
int tot = cnt; cnt=1;
for(int i=2;i<=tot;i++)
if(abs(cir[i]-cir[i-1])>eps)
cir[++cnt] = cir[i];
cir[cnt+1] = cir[1] + 2*pi;
for(int i=1;i<=cnt;i++)
{
db theta = (cir[i] + cir[i+1]); theta = theta/2.0;
mid[i] = vec(r*cosl(theta),r*sinl(theta));
}
if(cnt==2)
{
if(check(mid[1]))
{
db ang = cir[2] - cir[1];
ans += ang;
}
return ans;
}
for(int i=1;i<=cnt;i++)
{
if(check(mid[i]))
{
db ang = cir[i+1] - cir[i];
ans += ang;
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%Lf%Lf",&enemy[i].x,&enemy[i].y);
for(int i=1;i<=m;i++)
scanf("%Lf%Lf",&stk[i].x,&stk[i].y);
for(int i=1;i<m;i++)
li[i]=line(stk[i],stk[i+1]-stk[i]);
li[m] = line(stk[m],stk[1]-stk[m]);
db full,r,ans=0.0;
for(int i=1;i<=n;i++)
{
r = sqrtl(len(enemy[i]));
if(r<eps)
{
if(check(poi(0,0))) ans += 1.00000;
continue;
}
full = 2*pi;
ans += makecircle(i,r)/full;
}
printf("%.5Lf
",ans);
return 0;
}
/**
1 7
1 1
2 1
-1 -1
-1 1
1 1
1 2
3 1
2 -1
*/