J 小白兔小灰兔
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
Special Judge, 64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
Special Judge, 64bit IO Format: %lld
题目描述
老山羊伯伯在地里收白菜，小白兔和小灰兔看见了就一起来帮忙。
他们干了半天，终于干完了。
羊伯伯：小灰兔，这车白菜送给你！
小灰兔：谢谢羊伯伯！
羊伯伯：小白兔，我也送你一车白菜！
小白兔：我不要白菜！给我一包白菜种子吧！
羊伯伯：好！给你~
小白兔：谢谢羊伯伯~
小灰兔把白菜拉到家里之后，就跟大家梦想中的生活一样，躺着啥都不干，吃吃吃，吃了玩~（好想一辈子都这样啊~小灰兔心想。）
小白兔把种子拿回去，打算开始勤劳地种白菜。然而他发现不是所有土地都能用来种白菜，只有被阳光照到的地方可以种白菜。
小白兔生活的星球可以看作二维平面中的一个简单多边形，太阳可以看作一个点。小白兔想知道，这个星球上一共有长度多少的土地可以用来种白菜。
输入描述:
第一行是一个正整数T(≤ 20)，表示测试数据组数，
对于每组测试数据，
第一行是一个整数n(3≤ n≤ 10)，表示简单多边形的顶点数，
接下来n行，每行是两个整数xi,yi(-10≤ xi,yi≤10)，按照逆时针绕向给出简单多边形的n个顶点的坐标，
最后一行是两个整数x,y(-10≤ x,y≤10)，表示太阳的坐标，保证太阳在多边形外且不在多边形任意一条边所在直线上。
输出描述:
对于每组测试数据，输出一行，包含一个实数，表示可以用来种白菜的土地的总长度，要求相对误差不超过
，
也就是说，令输出结果为a，标准答案为b，若满足
，则输出结果会被认为是正确答案。
输入例子:
2
4
0 0
2 0
2 2
0 2
4 1
4
0 0
2 0
2 2
0 2
4 4
输出例子:
2.000000000000
4.000000000000
-->
示例1
输入
2
4
0 0
2 0
2 2
0 2
4 1
4
0 0
2 0
2 2
0 2
4 4
输出
2.000000000000
4.000000000000
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pbk pop_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
using namespace std;
typedef double db;
const int N=5e5+;
const db eps=1e-;
int equzero(db t)//带精度大小判断
{
if(t>eps) return ;
if(t<-eps) return -;
return ;
}
struct Point
{
db x,y;
Point(){}
Point(db _x,db _y):x(_x),y(_y) {}
Point operator +(const Point &b) const //+
{
return Point(x+b.x,y+b.y);
}
Point operator -(const Point &b) const//-
{
return Point(x-b.x,y-b.y);
}
Point operator *(const db &b) const// 放大
{
return Point(x*b,y*b);
}
Point operator /(const db &b) const//缩小
{
return Point (x/b,y/b);
}
db dot(const Point &b) const//点积
{
return x*b.x+y*b.y;
}
db det(const Point &b) const//叉积
{
return x*b.y-b.x*y;
}
bool operator ==(const Point &b) const
{
return equzero(x-b.x)== && equzero(y-b.y)==;
}
bool operator !=(const Point &b) const
{
return !(Point(x,y)==b);
}
db mo() //模
{
return sqrt(x*x+y*y);
}
}pt[N],u,v,mid;
struct Line
{
Point a,b;
Line (){}
Line (Point _a,Point _b):a(_a),b(_b) {};
bool quickrej(const Line &t) const//快速排斥判断
{
return equzero(min(a.x,b.x)-max(t.a.x,t.b.x))<= && equzero(min(t.a.x,t.b.x)-max(a.x,b.x))<= && equzero(min(a.y,b.y)-max(t.a.y,t.b.y))<= && equzero(min(t.a.y,t.b.y)-max(a.y,b.y))<=;
}
db len() const
{
return (b-a).mo();
}
bool stra(const Line &t) const //跨立判断
{
return equzero((a-t.a).det(t.b-t.a)*(b-t.a).det(t.b-t.a))< && equzero((t.a-a).det(b-a)*(t.b-a).det(b-a))< ;
}
bool gfxj(const Line &t) const //规范相交
{
return quickrej(t) && stra(t);
}
bool on(const Point &t) const //点在线段上
{
Line p=Line(a,b);
if(p.a.x>p.b.x)
swap(p.a,p.b);
if(equzero(t.x-p.a.x)< || equzero(t.x-p.b.x)>)
return false;
if(equzero((p.a-t).det(p.b-t))==)
return true;
else
return false;
}
bool kddxj(const Line &t) const //可多点相交
{
return quickrej(t) && (stra(t) || on(t.a) || on(t.b) || t.on(a) || t.on(b));
}
bool para(const Line &t) const // 平行或在一条直线上
{
return equzero((a.y-b.y)*(t.a.x-t.b.x)-(t.a.y-t.b.y)*(a.x-b.x))== ;
}
db operator & (const Line &t) const //返回切点占直线比例,距a比例
{
if(equzero((a-b).det(t.a-t.b))==)return -INF;
db tk=((a-t.a).det(t.a-t.b))/((a-b).det(t.a-t.b));
return equzero(tk)>= && equzero(tk-)<= ? tk : -INF;
}
}le[N],lu,lv;
int n,m,T;
vector<db> cp;
db ans,ins,rate;
bool flag;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lf%lf",&pt[i].x,&pt[i].y);
for(int i=;i<n;i++)
le[i]=Line(pt[i],pt[(i+)%n]);
ans=;
for(int i=;i<n;i++)
{
cp.clear();
for(int j=;j<n;j++)
{
ins=le[i]&Line(pt[n],pt[j]);
if(ins>=-) cp.pb(ins);
}
sort(cp.begin(),cp.end());
rate=;
for(int j=;j<cp.size()-;j++)
{
lu=Line(pt[n],le[i].a+(le[i].b-le[i].a)*((cp[j]+cp[j+])/));
flag=;
for(int k=;k<n;k++)
{
if(lu.gfxj(le[k]))
{
flag=;
break;
}
}
if(!flag)
{
rate+=cp[j+]-cp[j];
}
}
ans+=rate*le[i].len();
}
printf("%.12f\n",ans);
}
return ;
}