{
double x,y;
//int x,y;
//Point(int x=0,int y=0):x(x),y(y){}
Point(double x=0,double y=0):x(x),y(y){}
void show()
{
//printf("(%d,%d)\n",x,y);
printf("(%.5lf,%.5lf)\n",x,y);
}
}p[200];
Point operator+(Point A,Point B){return (Point){A.x+B.x,A.y+B.y};} //向量A+B
Point operator-(Point A,Point B){return (Point){A.x-B.x,A.y-B.y};} //向量A-B
Point operator*(Point A,double B){return (Point){A.x*B,A.y*B};} //向量A*B
Point operator/(Point A,double B){return (Point){A.x/B,A.y/B};} //向量A/B
double operator*(Point A,Point B){return A.x*B.x+A.y*B.y;} //向量A B的点积
double operator^(Point A,Point B){return A.x*B.y-A.y*B.x;} //向量A B的叉积
double cross(Point A,Point B){return A.x*B.y-A.y*B.x;} //向量A B的叉积
double dis(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));} //A B两点的距离
int operator==(const Point&A,const Point&B){return A.x==B.x&&A.y==B.y;}//判断A B两点是否相等
int ison(Point x,Point st,Point en){return ((st-x)*(en-x))<=0&&((st-x)^(en-x))==0;}
//判断点x是否在直线ab上
int pointonseg(Point x,Point a,Point b){return (x.x-a.x)*(b.y-a.y)-(b.x-a.x)*(x.y-a.y)==0;}
int segmentin1(Point a1,Point a2,Point b1,Point b2)//判断以a1-a2和以b1-b2为对角线的矩形是否相交
{
if(min(a1.x,a2.x) > max(b1.x,b2.x) ||
min(b1.x,b2.x) > max(a1.x,a2.x) ||
min(a1.y,a2.y) > max(b1.y,b2.y) ||
min(b1.y,b2.y) > max(a1.y,a2.y) )return 0;
return 1;
}
int segmentin(Point a1,Point a2,Point b1,Point b2)
{
if(segmentin1(a1,a2,b1,b2)==0)return 0;
double c1=(a2-a1)^(b1-a1),c2=(a2-a1)^(b2-a1);
double c3=(b2-b1)^(a1-b1),c4=(b2-b1)^(a2-b1);
if(c1*c2>0&&c3*c4>0)return 0; //线段不相交
if((c1==0&&c2==0)||(c3==0&&c4==0))return -1;//线段部分重合
if(c1*c2<0&&c3*c4<0)return 1; //规范相交
return 2; //端点处相交
}
Point getaxi(Point a,Point b,Point c,Point d)
{
Point u=a-c;
Point v=b-a;
Point w=d-c;
double t=(w^u)/(v^w);
return a+v*t;
}
//点P到直线AB距离
double Distoline(Point P,Point A,Point B){return fabs(cross(B-A,P-A))/dis(A,B);}
double Polyarea(Point *p,int n) //求多边形面积(任意形状都可)
{
double area=0;
for(int i=1;i<n-1;i++)area+=(p[i]-p[0])^(p[i+1]-p[0]);
return fabs(area/2);
}
int cmp(const Point& x,const Point& y) //求凸包
{
if(x.x==y.x)return x.y<=y.y;
return x.x<y.x;
}
int Tu(Point *p,int n,Point *ch) //求凸包
{
sort(p,p+n,cmp);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
ch[m++]=p[i];
}
if(n>1)m--;
return m;
}
//判断点x是否在多边形内
int ispointonse(Point x,Point *p,int n)
{
int wn=0;
for(int i=0;i<n;i++)
{
if(ison(x,p[i],p[(i+1)%n]))return -1; //点在多边形边界上
double k=(p[(i+1)%n]-p[i])^(x-p[i]);
double d1=p[i].y-x.y;
double d2=p[(i+1)%n].y-x.y;
if(k>1e-10&&d1<=0&&d2>1e-10)wn++;
if(k<0&&d2<=0&&d1>1e-10)wn--;
}
if(wn)return 1; //点在多边形内
return 0; //点在多边形外
}
//向量旋转公式(一条线段以一个端点为圆心，线段长为半径，旋转angle度后的另一个端点的坐标)
x1=(x-x0)*cos(angle)-(y-y0)*sin(angle)+x0; //(x0,y0)为圆心
y1=(x-x0)*sin(angle)+(y-y0)*cos(angle)+y0; //(x1,y1)为旋转angle度后的另一个端点坐标
正n边形面积公式
S=n*R*R*sin(360/n)/2 (R为正n边形外接圆的半径)
n个点，求每一对点的距离的和。
设n个点坐标(x1,y1),(x2,y2),(x3,y3).....(xn,yn)
sum=(x1*x1+y1*y1+x2*x2+y2*y2+...xn*xn+yn*yn)-(x1+x2+x3+...+xn)^2-(y1+y2+y3+..+yn)^2
三角形重心公式
a(x1,y1) b(x2,y2) c(x3,y3)
x=(x1+x2+x3)/3;
y=(y1+y2+y3)/3;
费马点:三角形内且到三角形三个顶点距离之和最短的点
(x,y)为三角形ABC的费马点
x=sin(A)/sin(A+PI/3)*Xa+sin(B)/sin(B+PI/3)*Xb+sin(C)/sin(C+PI/3)*Xc;
y=sin(A)/sin(A+PI/3)*Ya+sin(B)/sin(B+PI/3)*Yb+sin(C)/sin(C+PI/3)*Yc;
任意凸四边形两对角线交点即为任意凸四边形的费马点
三角形外接圆圆心公式
x=( (x1*x1-x2*x2+y1*y1-y2*y2)*(y1-y3)-(x1*x1-x3*x3+y1*y1-y3*y3)*(y1-y2) ) / (2*(y1-y3)*(x1-x2)-2*(y1-y2)*(x1-x3));
y=( (x1*x1-x2*x2+y1*y1-y2*y2)*(x1-x3)-(x1*x1-x3*x3+y1*y1-y3*y3)*(x1-x2) ) / (2*(y1-y2)*(x1-x3)-2*(y1-y3)*(x1-x2));
三角形内切圆圆心公式
a,b,c分别为三角形三边长度
x=(a*x1+b*x2+c*x3)/(a+b+c);
y=(a*y1+b*y2+c*y3)/(a+b+c);
p=(a+b+c)/2;
r=2*sqrt(p*(p-a)*(p-b)*(p-c))/(a+b+c);
已知圆1(x1,y1) 半径r1 圆2(x2,y2) 半径r2 求相交点(x3,y3) (x4,y4)
double distance=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
double adis=(r1*r1-r2*r2+distance*distance)/(2*distance);
double h=sqrt(r1*r1-adis*adis);
double x=x1+(x2-x1)*adis/distance;
double y=y1+(y2-y1)*adis/distance;
double x3=x+h*(y2-y1)/distance; double x4=x-h*(y2-y1)/distance;
double y3=y-h*(x2-x1)/distance; double y4=y+h*(x2-x1)/distance;
笛卡尔定理：
定义一个圆的曲率k=+1/r或-1/r，其中是其半径。
若平面有两两相切，且有6个独立切点的四个圆，设其曲率为k1,k2,k3,k4（若该圆与其他圆均外切，则曲率取正，否则取负）则其满足性质：
（k1+k2+k3+k4）*（k1+k2+k3+k4）=2*（k1*k1+k2*k2+k3*k3+k4*k4）