|
}
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[10010],ch[10010];
int main(){
int n,T,cas=1;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
double sumx=0,sumy=0;
for(int i=0;i
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const double eps=1e-10;//精度
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
int dcmp(double x){//判断double等于0或。。。
if(fabs(x) Polygon;
Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}//向量+向量=向量
Vector operator-(Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}//点-点=向量
Vector operator*(Vector a,double p){return Vector(a.x*p,a.y*p);}//向量*实数=向量
Vector operator/(Vector a,double p){return Vector(a.x/p,a.y/p);}//向量/实数=向量
bool operator<( const Point& A,const Point& B ){return dcmp(A.x-B.x)<0||(dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)<0);}
bool operator==(const Point&a,const Point&b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}
bool operator!=(const Point&a,const Point&b){return a==b false:true;}
struct Segment{
Point a,b;
Segment(){}
Segment(Point _a,Point _b){a=_a,b=_b;}
bool friend operator<(const Segment& p,const Segment& q){return p.a0) return tempa-tempb;
else return tempa-tempb+2*PI;
}
double torad(double deg){return deg/180*PI;}//角度化为弧度
Vector Rotate(Vector a,double rad){//向量逆时针旋转rad弧度
return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
Vector Normal(Vector a){//计算单位法线
double L=Length(a);
return Vector(-a.y/L,a.x/L);
}
Point GetLineProjection(Point p,Point a,Point b){//点在直线上的投影
Vector v=b-a;
return a+v*(Dot(v,p-a)/Dot(v,v));
}
Point GetLineIntersection(Point p,Vector v,Point q,Vector w){//求直线交点 有唯一交点时可用
Vector u=p-q;
double t=Cross(w,u)/Cross(v,w);
return p+v*t;
}
int ConvexHull(Point* p,int n,Point* sol){//计算凸包
sort(p,p+n);
int m=0;
for(int i=0;i1&&Cross(sol[m-1]-sol[m-2],p[i]-sol[m-2])<=0) m--;
sol[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--){
while(m>k&&Cross(sol[m-1]-sol[m-2],p[i]-sol[m-2])<=0) m--;
sol[m++]=p[i];
}
if(n>0) m--;
return m;
}
double Heron(double a,double b,double c){//海伦公式
double p=(a+b+c)/2;
return sqrt(p*(p-a)*(p-b)*(p-c));
}
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){//线段规范相交判定
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
double CutConvex(const int n,Point* poly, const Point a,const Point b, vector result[3]){//有向直线a b 切割凸多边形
vector points;
Point p;
Point p1=a,p2=b;
int cur,pre;
result[0].clear();
result[1].clear();
result[2].clear();
if(n==0) return 0;
double tempcross;
tempcross=Cross(p2-p1,poly[0]-p1);
if(dcmp(tempcross)==0) pre=cur=2;
else if(tempcross>0) pre=cur=0;
else pre=cur=1;
for(i |