【计算几何】二维基础 （丑陋的）板子

符号判断与大小比较

int sgn(int x){
	if(fabs(x)<eps)return 0;
	else if(x>=eps)return 1;
	else return -1;
}

//实数的向上取整函数
int _ceil(const double &x)
{
    long long k=ceil(x);
    while (k<x) k++;
    while (k>x+1) k--;
    return k;
}

点

struct Point{
	double x,y; //坐标定义 部分题目可以使用int 
	void input(){scanf("%lf%lf",&x,&y);};
	void output(){printf("%.6lf %.6lf\n",x,y);};//注意输出精度
	Point operator+(const Point &a) const {return {x+a.x,y+a.y};}//两个点相加
    Point operator-(const Point &a) const {return {x-a.x,y-a.y};}
    Point operator-() const {return {-x,-y};}
    Point operator*(const double k) const {return {k*x,k*y};}//注意k和点的先后顺序
    Point operator/(const double k) const {return {x/k,y/k};}
    double operator*(const Point &a) const {return x*a.x+y*a.y;} //Dot
    double operator^(const Point &a) const {return x*a.y-y*a.x;} //Cross
	double dis(Point a){
		return sqrt((a.x-x)*(a.x-x)+(a.y-y)*(a.y-y));
	}//两点之间距离 使用方式 b.dis(a);
};

直线

struct Line{
	Point p,v;//l=p+tv 理解的时候注意方向向量和单位方向向量的区别
};

to-left检测

//已知一点和一条直线，求点c与直线的相对位置
int to_left(Line l,Point c){
	Point a=l.p,b=l.p+l.v;
	Point X={b.x-a.x,b.y-a.y},Y={c.x-a.x,c.y-a.y};
	int ans=X.x*Y.y-X.y*Y.x;//差积
    if(abs(ans)<eps)return 0;//在直线上
    else if(ans>0)return 1;//在直线左侧
    return -1;//在直线右侧
}

//已知三个点，求点c与点AB构成的直线的相对位置
int to_left(Point a,Point b,Point c){
	Point X={b.x-a.x,b.y-a.y},Y={c.x-a.x,c.y-a.y};
	int ans=X.x*Y.y-X.y*Y.x;//差积
    if(abs(ans)<eps)return 0;//在直线上
    else if(ans>0)return 1;//在直线左侧
    return -1;//在直线右侧
}

直线交点

//判断两直线是否会有交点
bool is_intt(Line l,Point a,Point b){
	return to_left(l,a)*to_left(l,b)<=0;
}

//求两直线交点
Point getjd(Line l,Line a){
	return l.p+l.v*((a.v^(l.p-a.p))/(l.v^a.v));
}