【计算几何】计算几何点，线，圆定义及相关模板

代码来源

#include <bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 200009
#define INF 1e18
#define Pair pair<LL,LL>
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-6
#define mod 99999997

int sgn(double x);
int dcmp(double x,double y);
double nround(double x,int t); // 四舍五入保留n位小数 , (保留3位小数)1.2100 => 1.21; 

struct Point{
	double x,y;
	Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector; // 向量 
Vector operator + (Vector A,Vector B);
Vector operator - (Vector A,Vector B);
Vector operator * (Vector A,double k);
Vector operator / (Vector A,double k);
bool operator < (const Point& a,const Point& b);
bool operator == (const Point& a,const Point& b);
bool PolarAngleCmp(Point a,Point b,Point start); // 极角排序 
bool PolarAngleCmp2(Point a,Point b,Point start); // 极角排序另一种方法，速度快
double Dot(Vector A,Vector B); 		// 内积  α·β=|α||β|cosθ
double Cross(Vector A, Vector B);	// 外积  α×β=|α||β|sinθ
double Cross(Point a,Point b,Point c); 
double Dis(Point a,Point b);		// 两点距离 
double Length(Vector A);			// 向量取模 
double Angle(Vector A,Vector B);	// 计算两向量夹角 返回值为弧度制下的夹角 
double Area2(Point a,Point b,Point c); 	// 计算两向量构成的平行四边形有向面积 
double Area2(Vector A,Vector B);	// 计算两向量构成的平行四边形有向面积 
Vector Rotate(Vector A,double rad);	// 计算向量逆时针旋转后的向量 
Vector Normal(Vector A);	 		// 计算向量逆时针旋转九十度的单位法向量 
bool ToLeftTest(Point a,Point b,Point c);	//判断折线bc是不是向ab的逆时针方向（左边）转向
double ClosePoint(vector<Point> &vc,int l,int r); // 平面最近点对 [l,r] 
//Andrew算法 计算凸包，输入点数组为 p，个数为 n， 输出点数组为 ch。函数返回凸包顶点数
int Andrew_ConvexHull(Point* p, int n, Point* ch); 
//Graham扫描法 计算凸包 
int Graham_ConvexHull(Point* p, int n, Point* cc);

struct Line{ // 定义直线 ,参数方程 
	Point v, p; // 直线上两点 ,以 v 为起点 
	Line(Point v={0,0},Point p={0,0}):v(v),p(p){}
	Point point(double t){
		return v + (p-v)*t;
	}
}; 
//计算两直线交点，必须保证直线相交，否则将会出现除以零的情况 
//调用前需保证 Cross(v, w) != 0
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w);
//点P到直线AB距离公式(取绝对值) 
double DistanceToLine(Point P,Point A,Point B);
//计算点到线段的距离
//点P到线段AB距离公式
double DistanceToSegment(Point P,Point A,Point B);
//点P在直线AB上的投影点
Point GetLineProjection(Point P, Point A, Point B);
//判断点是否在线段上
bool OnSegment(Point p, Point a1, Point a2);
//判断两线段是否相交
//通过两次跨立实验
//不允许在顶点处相交
bool SegmentProperIntersectionNo(Point a1, Point a2, Point b1, Point b2);
//允许在端点处相交
bool SegmentProperIntersectionYes(Point a1, Point a2, Point b1, Point b2);
//求多边形面积  p为端点集合，n为端点个数 [0,n) 
double PolygonArea(Point* p, int n);
//判断点是否在多边形内，若点在多边形内返回1，在多边形外部返回0，在多边形上返回-1
int isPointInPolygon(Point p, vector<Point> poly);

//计算机中储存圆通常记录圆心坐标与半径
struct Circle{
    Point c;
    double r;
    Circle(Point c={0,0}, double r=0):c(c), r(r) {}
    Point point(double a){//通过圆心角求坐标
        return Point(c.x + cos(a)*r, c.y + sin(a)*r);
    }
};
// 判断点在圆内 
bool PointInCircle(Point A,Circle C);
//求圆与直线交点 返回t1,t2,存放于sol中 
int getLineCircleIntersection(Line L, Circle C, double& t1, double& t2, vector<Point>& sol);
//两圆相交面积 通过计算两个圆相交所构成的两个扇形面积和减去其构成的筝形的面积
double AreaOfOverlap(Point c1, double r1, Point c2, double r2);

LL n,m,k;
Point p[MS];
Point tubao[MS];

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> p[i].x >> p[i].y;
	}
	if(n <= 1){
		printf("0.00\n");
		return 0;
	}
	int cnt = Graham_ConvexHull(p,n,tubao);
	double ans = Dis(tubao[0],tubao[cnt-1]);
	if(cnt == 2){
		printf("%.2f\n",ans);
		return 0;
	}
	for(int i=1;i<cnt;i++){
		ans += Dis(tubao[i-1],tubao[i]);
	}
	printf("%.2f\n",ans);
	
	
	return 0;
}



// floor(x) 向下取整
// ceil(x)  向上取整
// round(x) 四舍五入 

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

int dcmp(double x,double y){
	if(fabs(x-y) < eps) return 0;
	if(x > y) return 1;
	return -1;
}

// 四舍五入保留n位小数 , (保留3位小数)1.2100 => 1.21; 
double nround(double x,int t){
	LL k = pow(10,t);
	double cc = x*k;
	cc = round(cc);
	return cc/k;
}

Vector operator + (Vector A,Vector B){
	return Point(A.x+B.x,A.y+B.y);
}

Vector operator - (Vector A,Vector B){
	return Vector(A.x-B.x,A.y-B.y);
}

Vector operator * (Vector A,double k){
	return Vector(A.x*k,A.y*k);
}

Vector operator / (Vector A,double k){
	return Vector(A.x/k,A.y/k);
}

bool operator < (const Point& a,const Point& b){ // 从左下到右 
	if(a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

bool operator == (const Point& a,const Point& b){
	if(sgn(a.x-b.x) == 0 && sgn(a.y-b.y)) return true;
	return false;
}

/* α·β=|α||β|cosθ

向量α在向量β的投影α′（带有方向性）与β的长度乘积

若α与β的夹角为锐角，则其内积为正

若α与β的夹角为钝角，则其内积为负

若α与β的夹角为直角，则其内积为0 */

double Dot(Vector A,Vector B){ // 内积  α·β=|α||β|cosθ
	return A.x*B.x+A.y*B.y; 
}

/*α×β=|α||β|sinθ

θ 表示向量α旋转到向量β所经过的夹角 (右手定则)

若β在α的逆时针方向，则为正值

顺时针则为负值

两向量共线则为0 */ 

double Cross(Vector A, Vector B){ // 外积  α×β=|α||β|sinθ
    return A.x*B.y-A.y*B.x;
}

double Cross(Point a,Point b,Point c){ // ab x ac
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

double Dis(Point a,Point b){//计算距离
    return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));
}

double Length(Vector A){ // 向量取模 
	return sqrt(Dot(A,A));
}

double Angle(Vector A,Vector B){ //计算两向量夹角 返回值为弧度制下的夹角 
	return acos( Dot(A,B) / (Length(A)*Length(B)) );
}

double Area2(Point a,Point b,Point c){ // 计算两向量构成的平行四边形有向面积 
	return Cross(b-a,c-a);
}

double Area2(Vector A,Vector B){ // 计算两向量构成的平行四边形有向面积 
	return Cross(A,B);
}

Vector Rotate(Vector A,double rad){ // 计算向量逆时针旋转后的向量 
	return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}

Vector Normal(Vector A){ // 计算向量逆时针旋转九十度的单位法向量 
	double len = Length(A);
	return Vector(-A.y/len ,A.x/len);
}

bool ToLeftTest(Point a,Point b,Point c){ //判断折线bc是不是向ab的逆时针方向（左边）转向
	return Cross(b-a,c-b) > 0;
}

//平面最近点对
double ClosePoint(vector<Point> &vc,int l,int r){
	if(r-l<=5){
		double ans = DBINF;
		for(int i=l;i<=r;i++){
			for(int j=i+1;j<=r;j++){
				ans = min(ans,Length(vc[i]-vc[j]));
			}
		}
		return ans;
	} 
	int m = l+r>>1;
	double ans = min(ClosePoint(vc,l,m),ClosePoint(vc,m+1,r));
	vector<Point> tvc;
	for(int i=l;i<=r;i++){
		if(abs(vc[i].x - vc[m].x) <= ans){
			tvc.push_back(vc[i]);
		}
	}
	sort(tvc.begin(),tvc.end(),[](Point k1,Point k2){return k1.y<k2.y;});
	for(int i=0;i<tvc.size();i++){
		for(int j=i+1;j<tvc.size() && tvc[j].y-tvc[i].y<ans;j++){
			ans = min(ans,Length(tvc[i]-tvc[j]));
		}
	}
	return ans;
} 

//计算两直线交点，必须保证直线相交，否则将会出现除以零的情况 
//调用前需保证 Cross(v, w) != 0
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){
	Vector u = P-Q;
	double t = Cross(w,u)/Cross(v,w);
	return P+v*t;
}

//点P到直线AB距离公式
double DistanceToLine(Point P,Point A,Point B){
	Vector v1 = B-A, v2 = P-A;
	return fabs(Cross(v1,v2)/Length(v1));
}//不取绝对值，得到的是有向距离

//计算点到线段的距离
//点P到线段AB距离公式
double DistanceToSegment(Point P,Point A,Point B){
	if(A == B) return Length(P-A);
	Vector v1 = B-A ,v2 = P-A ,v3 = P-B;
	if(sgn(Dot(v1,v2)) < 0) return Length(v2);
	if(sgn(Dot(v1,v3)) > 0) return Length(v3);
	return DistanceToLine(P,A,B);
}

//点P在直线AB上的投影点
Point GetLineProjection(Point P, Point A, Point B){
    Vector v = B-A;
    return A+v*(Dot(v, P-A)/Dot(v, v));
}

//判断点是否在线段上
bool OnSegment(Point p, Point a1, Point a2){
    return sgn(Cross(a1-p, a2-p)) == 0 && sgn(Dot(a1-p, a2-p)) < 0;
}

//判断两线段是否相交
//通过两次跨立实验
//不允许在顶点处相交
bool SegmentProperIntersectionNo(Point a1, Point a2, Point b1, Point b2){
    double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1);
    double c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
    return (sgn(c1)*sgn(c2) < 0 && sgn(c3)*sgn(c4) < 0);
}

//允许在端点处相交
bool SegmentProperIntersectionYes(Point a1, Point a2, Point b1, Point b2){
    double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);
    double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
    //if判断控制是否允许线段在端点处相交，根据需要添加
    if(!sgn(c1) || !sgn(c2) || !sgn(c3) || !sgn(c4)){
        bool f1 = OnSegment(b1, a1, a2);
        bool f2 = OnSegment(b2, a1, a2);
        bool f3 = OnSegment(a1, b1, b2);
        bool f4 = OnSegment(a2, b1, b2);
        bool f = (f1|f2|f3|f4);
        return f;
    }
    return (sgn(c1)*sgn(c2) < 0 && sgn(c3)*sgn(c4) < 0);
}

//求多边形面积
double PolygonArea(Point* p, int n){//p为端点集合，n为端点个数
    double s = 0;
    for(int i = 1; i < n-1; ++i)
        s += Cross(p[i]-p[0], p[i+1]-p[0]);
    return fabs(s/2.0);
}

//判断点是否在多边形内，若点在多边形内返回1，在多边形外部返回0，在多边形上返回-1
int isPointInPolygon(Point p, vector<Point> poly){
    int wn = 0;
    int n = poly.size();
    for(int i = 0; i < n; ++i){
        if(OnSegment(p, poly[i], poly[(i+1)%n])) return -1;
        int k = sgn(Cross(poly[(i+1)%n] - poly[i], p - poly[i]));
        int d1 = sgn(poly[i].y - p.y);
        int d2 = sgn(poly[(i+1)%n].y - p.y);
        if(k > 0 && d1 <= 0 && d2 > 0) wn++;
        if(k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    if(wn != 0)
        return 1;
    return 0;
}

// 判断点在圆内 
bool PointInCircle(Point A,Circle C){
	Vector p = A-C.c;
	return Length(p) < C.r; 
}

//求圆与直线交点
int getLineCircleIntersection(Line L, Circle C, double& t1, double& t2, vector<Point>& sol){
    double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
    double e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
    double delta = f*f - 4*e*g;//判别式
    if(sgn(delta) < 0)//相离
        return 0;
    if(sgn(delta) == 0){//相切
        t1 = -f /(2*e);
        t2 = -f /(2*e);
        sol.push_back(L.point(t1));//sol存放交点本身
        return 1;
    }
    //相交
    t1 = (-f - sqrt(delta))/(2*e);
    sol.push_back(L.point(t1));
    t2 = (-f + sqrt(delta))/(2*e);
    sol.push_back(L.point(t2));
    return 2;
}

//两圆相交面积 通过计算两个圆相交所构成的两个扇形面积和减去其构成的筝形的面积
double AreaOfOverlap(Point c1, double r1, Point c2, double r2){
    double d = Length(c1 - c2);
    if(r1 + r2 < d + eps)
        return 0.0;
    if(d < fabs(r1 - r2) + eps){
        double r = min(r1, r2);
        return Pi*r*r;
    }
    double x = (d*d + r1*r1 - r2*r2)/(2.0*d);
    double p = (r1 + r2 + d)/2.0;
    double t1 = acos(x/r1);
    double t2 = acos((d - x)/r2);
    double s1 = r1*r1*t1;
    double s2 = r2*r2*t2;
    double s3 = 2*sqrt(p*(p - r1)*(p - r2)*(p - d));
    return s1 + s2 - s3;
}

//Andrew算法 计算凸包，输入点数组为 p，个数为 n， 输出点数组为 ch。函数返回凸包顶点数
//如果不希望凸包的边上有输入点，则把两个 <= 改为 <
//在精度要求高时建议用dcmp比较
//输入不能有重复点，函数执行完后输入点的顺序被破坏
int Andrew_ConvexHull(Point* p, int n, Point* ch) {
    sort(p, p+n);
    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;
}

//Graham扫描法 计算凸包 
double xx,yy;
int Graham_ConvexHull(Point* p, int n, Point* cc){
	if(n == 0) return 0;
	if(n == 1){
		cc[0] = p[0];
		return 1;
	}
	sort(p,p+n);
	int cnt = 0;
	cc[cnt++] = p[0];
	xx = p[0].x;
	yy = p[0].y;
	sort(p+1,p+n,[](Point a,Point b){ // 极角排序 2 
		if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
        	return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
    	return a.x<b.x;
	});
	cc[cnt++] = p[1];
	for(int i=2;i<n;i++){
		while(Cross(cc[cnt-2],cc[cnt-1],p[i]) < 0) cnt--;
		cc[cnt++] = p[i];
	} 
	return cnt;
}