UVA 10652 Board Wrapping (三)
ent(Point p,Segment s){
return dcmp(Cross(s.a-p,s.b-p))==0&&dcmp(Dot(s.a-p,s.b-p))<0;
}
int isPointInPolygon(Point p, Point* poly,int n){//点与多边形的位置关系
int wn=0;
for(int i=0;i0&&d1<=0&&d2>0)wn++;
if(k<0&&d2<=0&&d1>0)wn--;
}
if(wn) return 1;//点在内部
else return 0;//点在外部
}
double PolygonArea(Point* p,int n){//多边形有向面积
double area=0;
for(int i=1;iCross(ch[q]-ch[p+1],ch[p]-ch[p+1]))
q=(q+1)%n;
ans=max(ans,max(Length(ch[p]-ch[q]),Length(ch[p+1]-ch[q+1])));
}
return ans;
}
Polygon CutPolygon(Polygon poly,Point a,Point b){//用a->b切割多边形 返回左侧
Polygon newpoly;
int n=poly.size();
for(int i=0;i
=0) newpoly.push_back(c);
if(dcmp(Cross(b-a,c-d))!=0){
Point ip=GetLineIntersection(a,b-a,c,d-c);
if(isPointOnSegment(ip,Segment(c,d))) newpoly.push_back(ip);
}
}
return newpoly;
}
int GetCircleCircleIntersection(Circle c1,Circle c2,Point& p1,Point& p2){
double d=Length(c1.c-c2.c);
if(dcmp(d)==0){
if(dcmp(c1.r-c2.r)==0) return -1;//两圆重合
return 0;
}
if(dcmp(c1.r+c2.r-d)<0) return 0;
if(dcmp(fabs(c1.r-c2.r)-d)>0) return 0;
double a=Angle(c2.c-c1.c,Vector(1,0));
double da=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
p1=c1.point(a-da);p2=c1.point(a+da);
if(p1==p2) return 1;
return 2;
}
//--------------------------------------
//--------------------------------------
//--------------------------------------
//--------------------------------------
//--------------------------------------
int main(){
int T;
Point P[2500],ch[2500];
scanf("%d",&T);
while(T--){
int n,idx=0;
scanf("%d",&n);
double ans=0;
for(int i=0;i