计算几何题板整理

将一些计算几何常用的板整理一波

#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 1000
using namespace std;
inline double abs1(const double &a){
    return a>0?a:-a;
} 
struct Point{
    double x,y;
    friend Point operator +(const Point &a,const Point &b){
        return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator -(const Point &a,const Point &b){
        return Point(a.x-b.x,a.y-b.y);
    }
    friend bool operator <(const Point &a,const Point &b){
        return a.x==b.x?a.y<b.y:a.x<b.x;
    }
    friend bool operator >(const Point &a,const Point &b){
        return a.x==b.x?a.y>b.y:a.x>b.x;
    }
    friend  bool operator ==(const Point &a,const Point &b){
        return a.x==b.x&&a.y==b.y;
    } 
    friend double operator *(const Point &a,const Point &b){
        //叉乘 
        return a.x*b.y-b.x*a.y;
    }
    friend double operator &(const Point &a,const Point &b){
        //点乘 
        return abs1(a.x*b.x+a.y*b.y);
    }
    
    Point(){}
    Point(double a,double b){x=a;y=b;} 
}p[MAXN];
inline double len(const Point &a){
    //模长
    return sqrt(a.x*a.x+a.y*a.y); 
}
inline double trisize(const Point &a,const Point &b,const Point &c){
    //三角形面积
    return (a-c)*(b-c)/2; 
}
inline bool cmpangle(const Point &a,const Point &b){
    //极角排序
    return (a-p[0])*(b-p[0])>0; 
}
Point tb[MAXN];
int tbnum;
int tubao(const Point *a,int anum,Point *b){
    //极角排好序后求凸包
    int bnum=0; 
    b[bnum++]=a[0];
    b[bnum++]=a[1];
    for(int i=2;i<anum;i++){
        // 发现在栈里边一个顶点处没有向左转时，就把该顶点移除出去
        while(bnum>=2 && (b[bnum-2]-b[bnum-1])*(a[i]-b[bnum-1])>=0 )bnum--;
        b[bnum++]=a[i];
    }
    return bnum;
}
int main(){
//    Point a,b,c;
//    scanf("%lf %lf %lf %lf %lf %lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
//    printf("%f
",trisize(a,b,c));
//    p[0].x=4;p[0].y=2;
//    for(int i=0;i<=10;i++){
//        scanf("%lf %lf",&p[i].x,&p[i].y);
//        if(p[i]<p[0])swap(p[i],p[0]);
        //找到最左下角的点才能排序 
//    }
//    sort(p+1,p+1+10,cmpangle);
//    for(int i=1;i<=10;i++){
//        printf("%f %f
",p[i].x,p[i].y);
//    }
//    tbnum=tubao(p,11,tb);
//    for(int i=0;i<tbnum;i++){
//        printf("%f %f
",tb[i].x,tb[i].y);
//    }
    return 0;
}

tips：

点与凸包的关系，计算凸包每条边与点的叉乘，如果出现0，则在凸包边上，出现两个0，则在凸包顶点上，正负性均相同，则在凸包内，否则在凸包外。

线段与凸包的关系，是两个点与凸包的关系的笛卡尔积。

直线与凸包的关系，可求凸包上每点与直线叉乘的正负性。

两线段的关系，要先进行跨立判定，即两线段的外接长方形有无交。

两圆的关系，相离，相切，包含，同心都好说，若两圆相交，求交点，是用余弦定理求角度，有精度损失。