几何基础

1. 定义结构体 （表示点）

struct Point {double x,y;Point() {} Point(double a,double b) {x=a,y=b;}}point[N];

2.叉积

即 $a=(x1,y1)$，$b=(x2,y2)$ 则 $a imes b=x1*y2-x2*y1$

double det(double x1,double y1,double x2,double y2) {return x1*y2-x2*y1;}

叉积是有正负的，它是两个向量的又向四边形面积。

如果结果为负，则 $b$ 再 $a$ 的左侧，否则为右侧

3.判线段交

int exis(double t){ return (fabs(t)<=eps) ? 0 : (t < 0 ? -1 : 1 ) ;   }
double det(double x1,double y1,double x2,double y2) { return x1*y2-x2*y1;  }
double cross(Point a,Point b,Point c) { return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);  }
bool check(Point a,Point b,Point c,Point d) 
{
    if(exis(cross(a,c,b)) ^ exis(cross(a,d,b))==-2 && exis(cross(d,a,c)) ^ exis(cross(d,b,c)) == -2)  return true; 
    return false; 
}

4.