|
result[cur].push_back(p);
result[cur].push_back(poly[(i+1)%n]);
pre=cur;
}
}
sort(points.begin(),points.end());
if(points.size()<2){
return 0;
}
else{
return Length(points.front()-points.back());
}
}
double DistanceToSegment(Point p,Segment s){//点到线段的距离
if(s.a==s.b) return Length(p-s.a);
Vector v1=s.b-s.a,v2=p-s.a,v3=p-s.b;
if(dcmp(Dot(v1,v2))<0) return Length(v2);
else if(dcmp(Dot(v1,v3))>0) return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}
bool isPointOnSegment(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;
}
//两点式化为一般式A = b.y-a.y, B = a.x-b.x, C = -a.y*(B)-a.x*(A);
//--------------------------------------
//--------------------------------------
//--------------------------------------
//--------------------------------------
//--------------------------------------
Point P[400010],ch[400010];
int main(){
int n,T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
int idx=0;
for(int i=0;i
|