1.1 注意

1. 注意舍入方式(0.5 的舍入方向);防止输出-0.

2. 几何题注意多测试不对称数据.

3. 整数几何注意 xmult 和 dmult 是否会出界;

符点几何注意 eps 的使用.

4. 避免使用斜率;注意除数是否会为 0.

5. 公式一定要化简后再代入.

6. 判断同一个 2*PI 域内两角度差应该是

abs(a1-a2)<beta||abs(a1-a2)>pi+pi-beta;

相等应该是

abs(a1-a2)<eps||abs(a1-a2)>pi+pi-eps;

7. 需要的话尽量使用 atan2,注意:atan2(0,0)=0,

atan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.

8. cross product = |u|*|v|*sin(a)

dot product = |u|*|v|*cos(a)

9. (P1-P0)x(P2-P0)结果的意义:

正: <P0,P1>在<P0,P2>顺时针(0,pi)内

负: <P0,P1>在<P0,P2>逆时针(0,pi)内

0 : <P0,P1>,<P0,P2>共线,夹角为 0 或 pi

10. 误差限缺省使用 1e-8!

1.2 几何公式

三角形:1. 半周长 P=(a+b+c)/2

2. 面积 S=aHa/2=absin(C)/2=sqrt(P(P-a)(P-b)(P-c))

3. 中线 Ma=sqrt(2(b^2+c^2)-a^2)/2=sqrt(b^2+c^2+2bccos(A))/2

4. 角平分线 Ta=sqrt(bc((b+c)^2-a^2))/(b+c)=2bccos(A/2)/(b+c)

5. 高线 Ha=bsin(C)=csin(B)=sqrt(b^2-((a^2+b^2-c^2)/(2a))^2)

6. 内切圆半径 r=S/P=asin(B/2)sin(C/2)/sin((B+C)/2)

=4Rsin(A/2)sin(B/2)sin(C/2)=sqrt((P-a)(P-b)(P-c)/P)

=Ptan(A/2)tan(B/2)tan(C/2)

7. 外接圆半径 R=abc/(4S)=a/(2sin(A))=b/(2sin(B))=c/(2sin(C))

 

四边形:

D1,D2 为对角线,M 对角线中点连线,A 为对角线夹角

1. a^2+b^2+c^2+d^2=D1^2+D2^2+4M^2

2. S=D1D2sin(A)/2

(以下对圆的内接四边形)

3. ac+bd=D1D2

4. S=sqrt((P-a)(P-b)(P-c)(P-d)),P 为半周长

正 n 边形:

R 为外接圆半径,r 为内切圆半径

1. 中心角 A=2PI/n

2. 内角 C=(n-2)PI/n

3. 边长 a=2sqrt(R^2-r^2)=2Rsin(A/2)=2rtan(A/2)

4. 面积 S=nar/2=nr^2tan(A/2)=nR^2sin(A)/2=na^2/(4tan(A/2))

圆:

1. 弧长 l=rA

2. 弦长 a=2sqrt(2hr-h^2)=2rsin(A/2)

3. 弓形高 h=r-sqrt(r^2-a^2/4)=r(1-cos(A/2))=atan(A/4)/2

4. 扇形面积 S1=rl/2=r^2A/2

5. 弓形面积 S2=(rl-a(r-h))/2=r^2(A-sin(A))/2

棱柱:

1. 体积 V=Ah,A 为底面积,h 为高

2. 侧面积 S=lp,l 为棱长,p 为直截面周长

3. 全面积 T=S+2A

棱锥:

1. 体积 V=Ah/3,A 为底面积,h 为高

(以下对正棱锥)

2. 侧面积 S=lp/2,l 为斜高,p 为底面周长

3. 全面积 T=S+A

棱台:

1. 体积 V=(A1+A2+sqrt(A1A2))h/3,A1.A2 为上下底面积,h 为高

(以下为正棱台)

2. 侧面积 S=(p1+p2)l/2,p1.p2 为上下底面周长,l 为斜高

3. 全面积 T=S+A1+A2

27

圆柱:

1. 侧面积 S=2PIrh

2. 全面积 T=2PIr(h+r)

3. 体积 V=PIr^2h

圆锥:

1. 母线 l=sqrt(h^2+r^2)

2. 侧面积 S=PIrl

3. 全面积 T=PIr(l+r)

4. 体积 V=PIr^2h/3

圆台:

1. 母线 l=sqrt(h^2+(r1-r2)^2)

2. 侧面积 S=PI(r1+r2)l

3. 全面积 T=PIr1(l+r1)+PIr2(l+r2)

4. 体积 V=PI(r1^2+r2^2+r1r2)h/3

球:

1. 全面积 T=4PIr^2

2. 体积 V=4PIr^3/3

球台:

1. 侧面积 S=2PIrh

2. 全面积 T=PI(2rh+r1^2+r2^2)

3. 体积 V=PIh(3(r1^2+r2^2)+h^2)/6

球扇形:

1. 全面积 T=PIr(2h+r0),h 为球冠高,r0 为球冠底面半径

2. 体积 V=2PIr^2h/3

 

1.3、多边形

#include 
     
      #include 
      
       #define MAXN 1000#define offset 10000#define eps 1e-8#define zero(x) (((x)>0?(x):-(x))
       
        eps?1:((x)<-eps?2:0))struct point{
   double x,y;};struct line{point a,b;};double xmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);28}//判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线int is_convex(int n,point* p){int i,s[3]={
   1,1,1};for (i=0;i
        
         eps){t=barycenter(p[0],p[i],p[i+1]);ret.x+=t.x*t2;ret.y+=t.y*t2;t1+=t2;}if (fabs(t1)>eps)ret.x/=t1,ret.y/=t1;return ret;}
        
       
      
     

1.4 多边形切割

//多边形切割//可用于半平面交#define MAXN 100#define eps 1e-8#define zero(x) (((x)>0?(x):-(x))
     
      eps;}point intersection(point u1,point u2,point v1,point v2){point ret=u1;double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));ret.x+=(u2.x-u1.x)*t;ret.y+=(u2.y-u1.y)*t;return ret;}//将多边形沿 l1,l2 确定的直线切割在 side 侧切割,保证 l1,l2,side 不共线void polygon_cut(int& n,point* p,point l1,point l2,point side){point pp[100];int m=0,i;for (i=0;i
     

1.5 浮点函数

//浮点几何函数库#include 
     
      #define eps 1e-832#define zero(x) (((x)>0?(x):-(x))
      
       eps;}int same_side(point p1,point p2,point l1,point l2){return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;}//判两点在线段异侧,点在线段上返回 0int opposite_side(point p1,point p2,line l){return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)<-eps;}int opposite_side(point p1,point p2,point l1,point l2){return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;}//判两直线平行int parallel(line u,line v){return zero((u.a.x-u.b.x)*(v.a.y-v.b.y)-(v.a.x-v.b.x)*(u.a.y-u.b.y));}int parallel(point u1,point u2,point v1,point v2){return zero((u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y));}//判两直线垂直int perpendicular(line u,line v){return zero((u.a.x-u.b.x)*(v.a.x-v.b.x)+(u.a.y-u.b.y)*(v.a.y-v.b.y));34}int perpendicular(point u1,point u2,point v1,point v2){return zero((u1.x-u2.x)*(v1.x-v2.x)+(u1.y-u2.y)*(v1.y-v2.y));}//判两线段相交,包括端点和部分重合int intersect_in(line u,line v){if (!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b))return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u);}int intersect_in(point u1,point u2,point v1,point v2){if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);returndot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);}//判两线段相交,不包括端点和部分重合int intersect_ex(line u,line v){return opposite_side(u.a,u.b,v)&&opposite_side(v.a,v.b,u);}int intersect_ex(point u1,point u2,point v1,point v2){return opposite_side(u1,u2,v1,v2)&&opposite_side(v1,v2,u1,u2);}//计算两直线交点,注意事先判断直线是否平行!//线段交点请另外判线段相交(同时还是要判断是否平行!)point intersection(line u,line v){point ret=u.a;double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));ret.x+=(u.b.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;return ret;}point intersection(point u1,point u2,point v1,point v2){point ret=u1;double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));ret.x+=(u2.x-u1.x)*t;ret.y+=(u2.y-u1.y)*t;return ret;35}//点到直线上的最近点point ptoline(point p,line l){point t=p;t.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;return intersection(p,t,l.a,l.b);}point ptoline(point p,point l1,point l2){point t=p;t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;return intersection(p,t,l1,l2);}//点到直线距离double disptoline(point p,line l){return fabs(xmult(p,l.a,l.b))/distance(l.a,l.b);}double disptoline(point p,point l1,point l2){return fabs(xmult(p,l1,l2))/distance(l1,l2);}double disptoline(double x,double y,double x1,double y1,double x2,double y2){return fabs(xmult(x,y,x1,y1,x2,y2))/distance(x1,y1,x2,y2);}//点到线段上的最近点point ptoseg(point p,line l){point t=p;t.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;if (xmult(l.a,t,p)*xmult(l.b,t,p)>eps)return distance(p,l.a)
       
        eps)return distance(p,l1)
        
         eps)return distance(p,l.a)
         
          eps)return distance(p,l1)
         
        
       
      
     

1.6 面积

#include 
     
      struct point{
   double x,y;};//计算 cross product (P1-P0)x(P2-P0)double xmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}double xmult(double x1,double y1,double x2,double y2,double x0,double y0){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);}//计算三角形面积,输入三顶点double area_triangle(point p1,point p2,point p3){return fabs(xmult(p1,p2,p3))/2;}double area_triangle(double x1,double y1,double x2,double y2,double x3,double y3){return fabs(xmult(x1,y1,x2,y2,x3,y3))/2;}//计算三角形面积,输入三边长double area_triangle(double a,double b,double c){double s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c));}//计算多边形面积,顶点按顺时针或逆时针给出double area_polygon(int n,point* p){double s1=0,s2=0;int i;for (i=0;i
     

1.7 球面

#include 
     
      const double pi=acos(-1);//计算圆心角 lat 表示纬度,-90<=w<=90,lng 表示经度//返回两点所在大圆劣弧对应圆心角,0<=angle<=pidouble angle(double lng1,double lat1,double lng2,double lat2){double dlng=fabs(lng1-lng2)*pi/180;while (dlng>=pi+pi)dlng-=pi+pi;if (dlng>pi)dlng=pi+pi-dlng;lat1*=pi/180,lat2*=pi/180;return acos(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2));}//计算距离,r 为球半径double line_dist(double r,double lng1,double lat1,double lng2,double lat2){double dlng=fabs(lng1-lng2)*pi/180;while (dlng>=pi+pi)dlng-=pi+pi;if (dlng>pi)dlng=pi+pi-dlng;lat1*=pi/180,lat2*=pi/180;return r*sqrt(2-2*(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2)));}//计算球面距离,r 为球半径inline double sphere_dist(double r,double lng1,double lat1,double lng2,double lat2){return r*angle(lng1,lat1,lng2,lat2);}
     

 

 

1.8 三角形

#include 
     
      struct point{
   double x,y;};struct line{point a,b;};double distance(point p1,point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}point intersection(line u,line v){point ret=u.a;double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));ret.x+=(u.b.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;return ret;}//外心point circumcenter(point a,point b,point c){line u,v;u.a.x=(a.x+b.x)/2;u.a.y=(a.y+b.y)/2;u.b.x=u.a.x-a.y+b.y;u.b.y=u.a.y+a.x-b.x;v.a.x=(a.x+c.x)/2;v.a.y=(a.y+c.y)/2;v.b.x=v.a.x-a.y+c.y;v.b.y=v.a.y+a.x-c.x;return intersection(u,v);}//内心point incenter(point a,point b,point c){line u,v;double m,n;u.a=a;m=atan2(b.y-a.y,b.x-a.x);39n=atan2(c.y-a.y,c.x-a.x);u.b.x=u.a.x+cos((m+n)/2);u.b.y=u.a.y+sin((m+n)/2);v.a=b;m=atan2(a.y-b.y,a.x-b.x);n=atan2(c.y-b.y,c.x-b.x);v.b.x=v.a.x+cos((m+n)/2);v.b.y=v.a.y+sin((m+n)/2);return intersection(u,v);}//垂心point perpencenter(point a,point b,point c){line u,v;u.a=c;u.b.x=u.a.x-a.y+b.y;u.b.y=u.a.y+a.x-b.x;v.a=b;v.b.x=v.a.x-a.y+c.y;v.b.y=v.a.y+a.x-c.x;return intersection(u,v);}//重心//到三角形三顶点距离的平方和最小的点//三角形内到三边距离之积最大的点point barycenter(point a,point b,point c){line u,v;u.a.x=(a.x+b.x)/2;u.a.y=(a.y+b.y)/2;u.b=c;v.a.x=(a.x+c.x)/2;v.a.y=(a.y+c.y)/2;v.b=b;return intersection(u,v);}//费马点//到三角形三顶点距离之和最小的点point fermentpoint(point a,point b,point c){point u,v;double step=fabs(a.x)+fabs(a.y)+fabs(b.x)+fabs(b.y)+fabs(c.x)+fabs(c.y);int i,j,k;u.x=(a.x+b.x+c.x)/3;u.y=(a.y+b.y+c.y)/3;while (step>1e-10)for (k=0;k<10;step/=2,k++)for (i=-1;i<=1;i++)for (j=-1;j<=1;j++){v.x=u.x+step*i;v.y=u.y+step*j;if(distance(u,a)+distance(u,b)+distance(u,c)>distance(v,a)+distance(v,b)+distance(v,c))u=v;}return u;}
     

1.9 三维几何

//三维几何函数库#include 
     
      #define eps 1e-8#define zero(x) (((x)>0?(x):-(x))
      
       eps&&vlen(xmult(subt(p,s.b),subt(p,s.c)))>eps&&vlen(xmult(subt(p,s.c),subt(p,s.a)))>eps;}int dot_inplane_ex(point3 p,point3 s1,point3 s2,point3 s3){return dot_inplane_in(p,s1,s2,s3)&&vlen(xmult(subt(p,s1),subt(p,s2)))>eps&&vlen(xmult(subt(p,s2),subt(p,s3)))>eps&&vlen(xmult(subt(p,s3),subt(p,s1)))>eps;}//判两点在线段同侧,点在线段上返回 0,不共面无意义int same_side(point3 p1,point3 p2,line3 l){return dmult(xmult(subt(l.a,l.b),subt(p1,l.b)),xmult(subt(l.a,l.b),subt(p2,l.b)))>eps;}int same_side(point3 p1,point3 p2,point3 l1,point3 l2){return dmult(xmult(subt(l1,l2),subt(p1,l2)),xmult(subt(l1,l2),subt(p2,l2)))>eps;}//判两点在线段异侧,点在线段上返回 0,不共面无意义int opposite_side(point3 p1,point3 p2,line3 l){return dmult(xmult(subt(l.a,l.b),subt(p1,l.b)),xmult(subt(l.a,l.b),subt(p2,l.b)))<-eps;}int opposite_side(point3 p1,point3 p2,point3 l1,point3 l2){return dmult(xmult(subt(l1,l2),subt(p1,l2)),xmult(subt(l1,l2),subt(p2,l2)))<-eps;}//判两点在平面同侧,点在平面上返回 0int same_side(point3 p1,point3 p2,plane3 s){return dmult(pvec(s),subt(p1,s.a))*dmult(pvec(s),subt(p2,s.a))>eps;}int same_side(point3 p1,point3 p2,point3 s1,point3 s2,point3 s3){return dmult(pvec(s1,s2,s3),subt(p1,s1))*dmult(pvec(s1,s2,s3),subt(p2,s1))>eps;}//判两点在平面异侧,点在平面上返回 0int opposite_side(point3 p1,point3 p2,plane3 s){return dmult(pvec(s),subt(p1,s.a))*dmult(pvec(s),subt(p2,s.a))<-eps;}int opposite_side(point3 p1,point3 p2,point3 s1,point3 s2,point3 s3){return dmult(pvec(s1,s2,s3),subt(p1,s1))*dmult(pvec(s1,s2,s3),subt(p2,s1))<-eps;}//判两直线平行int parallel(line3 u,line3 v){return vlen(xmult(subt(u.a,u.b),subt(v.a,v.b)))
      
     

1.10 凸包

#include 
     
      #define eps 1e-8#define zero(x) (((x)>0?(x):-(x))
      
       0?1:-1):(ret>0?1:-1);}void _graham(int n,point* p,int& s,point* ch){int i,k=0;for (p1=p2=p[0],i=1;i
       
        eps||(zero(p1.y-p[i].y)&&p1.x>p[i].x))p1=p[k=i];p2.x/=n,p2.y/=n;p[k]=p[0],p[0]=p1;qsort(p+1,n-1,sizeof(point),graham_cp);for (ch[0]=p[0],ch[1]=p[1],ch[2]=p[2],s=i=3;i
        
         2&&xmult(ch[s-2],p[i],ch[s-1])<-eps;s--);}//构造凸包接口函数,传入原始点集大小 n,点集 p(p 原有顺序被打乱!)//返回凸包大小,凸包的点在 convex 中//参数 maxsize 为 1 包含共线点,为 0 不包含共线点,缺省为 1//参数 clockwise 为 1 顺时针构造,为 0 逆时针构造,缺省为 1//在输入仅有若干共线点时算法不稳定,可能有此类情况请另行处理!//不能去掉点集中重合的点int graham(int n,point* p,point* convex,int maxsize=1,int dir=1){point* temp=new point[n];int s,i;_graham(n,p,s,temp);for (convex[0]=temp[0],n=1,i=(dir?1:(s-1));dir?(i
        
       
      
     

网格

#define abs(x) ((x)>0?(x):-(x))struct point{
   int x,y;};int gcd(int a,int b){return b?gcd(b,a%b):a;}//多边形上的网格点个数int grid_onedge(int n,point* p){int i,ret=0;for (i=0;i

圆

#include 
     
      #define eps 1e-8struct point{
   double x,y;};double xmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}double distance(point p1,point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}double disptoline(point p,point l1,point l2){return fabs(xmult(p,l1,l2))/distance(l1,l2);}50point intersection(point u1,point u2,point v1,point v2){point ret=u1;double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));ret.x+=(u2.x-u1.x)*t;ret.y+=(u2.y-u1.y)*t;return ret;}//判直线和圆相交,包括相切int intersect_line_circle(point c,double r,point l1,point l2){return disptoline(c,l1,l2)
      
       -eps||t2>-eps;t.x+=l1.y-l2.y;t.y+=l2.x-l1.x;return xmult(l1,c,t)*xmult(l2,c,t)
       
        
         fabs(r1-r2)-eps;}//计算圆上到点 p 最近点,如 p 与圆心重合,返回 p 本身point dot_to_circle(point c,double r,point p){point u,v;if (distance(p,c)
        
       
      
     

1.13 整数函数

 

//整数几何函数库//注意某些情况下整数运算会出界!#define sign(a) ((a)>0?1:(((a)<0?-1:0)))struct point{
   int x,y;};struct line{point a,b;};//计算 cross product (P1-P0)x(P2-P0)int xmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int xmult(int x1,int y1,int x2,int y2,int x0,int y0){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);}//计算 dot product (P1-P0).(P2-P0)int dmult(point p1,point p2,point p0){return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);52}int dmult(int x1,int y1,int x2,int y2,int x0,int y0){return (x1-x0)*(x2-x0)+(y1-y0)*(y2-y0);}//判三点共线int dots_inline(point p1,point p2,point p3){return !xmult(p1,p2,p3);}int dots_inline(int x1,int y1,int x2,int y2,int x3,int y3){return !xmult(x1,y1,x2,y2,x3,y3);}//判点是否在线段上,包括端点和部分重合int dot_online_in(point p,line l){return !xmult(p,l.a,l.b)&&(l.a.x-p.x)*(l.b.x-p.x)<=0&&(l.a.y-p.y)*(l.b.y-p.y)<=0;}int dot_online_in(point p,point l1,point l2){return !xmult(p,l1,l2)&&(l1.x-p.x)*(l2.x-p.x)<=0&&(l1.y-p.y)*(l2.y-p.y)<=0;}int dot_online_in(int x,int y,int x1,int y1,int x2,int y2){return !xmult(x,y,x1,y1,x2,y2)&&(x1-x)*(x2-x)<=0&&(y1-y)*(y2-y)<=0;}//判点是否在线段上,不包括端点int dot_online_ex(point p,line l){return dot_online_in(p,l)&&(p.x!=l.a.x||p.y!=l.a.y)&&(p.x!=l.b.x||p.y!=l.b.y);}int dot_online_ex(point p,point l1,point l2){return dot_online_in(p,l1,l2)&&(p.x!=l1.x||p.y!=l1.y)&&(p.x!=l2.x||p.y!=l2.y);}int dot_online_ex(int x,int y,int x1,int y1,int x2,int y2){return dot_online_in(x,y,x1,y1,x2,y2)&&(x!=x1||y!=y1)&&(x!=x2||y!=y2);}//判两点在直线同侧,点在直线上返回 0int same_side(point p1,point p2,line l){return sign(xmult(l.a,p1,l.b))*xmult(l.a,p2,l.b)>0;}int same_side(point p1,point p2,point l1,point l2){return sign(xmult(l1,p1,l2))*xmult(l1,p2,l2)>0;}//判两点在直线异侧,点在直线上返回 053int opposite_side(point p1,point p2,line l){return sign(xmult(l.a,p1,l.b))*xmult(l.a,p2,l.b)<0;}int opposite_side(point p1,point p2,point l1,point l2){return sign(xmult(l1,p1,l2))*xmult(l1,p2,l2)<0;}//判两直线平行int parallel(line u,line v){return (u.a.x-u.b.x)*(v.a.y-v.b.y)==(v.a.x-v.b.x)*(u.a.y-u.b.y);}int parallel(point u1,point u2,point v1,point v2){return (u1.x-u2.x)*(v1.y-v2.y)==(v1.x-v2.x)*(u1.y-u2.y);}//判两直线垂直int perpendicular(line u,line v){return (u.a.x-u.b.x)*(v.a.x-v.b.x)==-(u.a.y-u.b.y)*(v.a.y-v.b.y);}int perpendicular(point u1,point u2,point v1,point v2){return (u1.x-u2.x)*(v1.x-v2.x)==-(u1.y-u2.y)*(v1.y-v2.y);}//判两线段相交,包括端点和部分重合int intersect_in(line u,line v){if (!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b))return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u);}int intersect_in(point u1,point u2,point v1,point v2){if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);returndot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);}//判两线段相交,不包括端点和部分重合int intersect_ex(line u,line v){return opposite_side(u.a,u.b,v)&&opposite_side(v.a,v.b,u);}int intersect_ex(point u1,point u2,point v1,point v2){return opposite_side(u1,u2,v1,v2)&&opposite_side(v1,v2,u1,u2);}