一坨计算几何的板子

一个辣鸡抄板选手。

//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
typedef long long LL;
typedef double db;
const int N=1e5+7;
const db eps=1e-10;
using namespace std;

template<typename T>void read(T &x)  {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}

struct pt {
    db x,y;
    pt(db x=0,db y=0):x(x),y(y){} 
}p[N],q[N]; 
typedef  pt vc; 

vc operator + (vc A,vc B) { return vc(A.x+B.x,A.y+B.y);}
vc operator - (vc A,vc B) { return vc(A.x-B.x,A.y-B.y);}
vc operator * (vc A,db p) { return vc(A.x*p,A.y*p);}
vc operator / (vc A,db p) { return vc(A.x/p,A.y/p);}
bool operator <(const vc&A,const vc&B) { return A.x<B.x||(A.x==B.x&&A.y<B.y);}
int dcmp(double x) { if(fabs(x)<eps) return 0; else return x<0?-1:1;}
bool operator == (const vc&A,const vc&B) { return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0; }

db dot(vc A,vc B) { return A.x*B.x+A.y*B.y; }
db length(vc A) { return sqrt(dot(A,A)); }
db angle(vc A,vc B) { return acos(dot(A,B)/length(A)/length(B)); }

db cross(vc A,vc B) { return A.x*B.y-A.y*B.x; }
db area2(pt A,pt B,pt C) { return cross(B-A,C-A);}

struct ln {
    pt a,b; db slop;
    friend bool operator <(const ln&A,const ln&B) {
        return A.slop==B.slop?cross(A.b-A.a,B.b-A.a)>0:A.slop<B.slop;
    }
}L[N],a[N],que[N];

//绕起点顺时逆时针a弧度
vc rotate(vc A,db rad) { return vc(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
//计算向量单位法线。需要先确保不是零向量
vc nomal(vc A) { db L=length(A); return vc(-A.y/L,A.x/L); } 

//cross(v,w)!=0
pt getlinejd(pt p,vc v,pt q,vc w) {
    vc u=p-q;
    db t=cross(w,u)/cross(v,w);
    return p+v*t;
}

db distoline(pt P,pt A,pt B) {
    vc v1=B-A,v2=P-A;
    return fabs(cross(v1,v2)/length(v1));
}

db distoseg(pt P,pt A,pt B) {
    if(A==B) return length(P-A);
    vc v1=B-A,v2=P-A,v3=P-B;
    if(dcmp(dot(v1,v2))<0) return length(v2);
    else if(dcmp(dot(v1,v3))<0) return length(v3);
    else return fabs(cross(v1,v2))/length(v1);
}

pt getlinety(pt P,pt A,pt B) {
    vc v=B-A;
    return A+v*(dot(v,P-A)/dot(v,v));
}

bool segxj(pt p1,pt p2,pt p3,pt p4) {
    if(!(max(p1.x,p2.x)>=min(p3.x,p4.x)+eps&&max(p3.x,p4.x)>min(p1.x,p2.x)+eps)
      &&(max(p1.y,p2.y)>=min(p3.y,p4.y)+eps&&max(p3.y,p4.y)>min(p1.y,p2.y)+eps)) return 0;
    if(cross(p3-p1,p2-p1)*cross(p4-p1,p2-p1)>eps) return 0;
    if(cross(p1-p3,p4-p3)*cross(p2-p3,p4-p3)>eps) return 0;
    return 1;
}

db polygonArea(pt p[],int n) {
    db res=0;
    for(int i=1;i<n-1;i++)
        res+=cross(p[i]-p[0],p[i+1]-p[0]);
    return res/2;
}

int main() {
    return 0;
}
基本操作
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
typedef long long LL;
typedef double db;
const db eps=1e-10;
const int N=50007;
using namespace std;
int n;

template<typename T>void read(T &x)  {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}

struct pt {
    db x,y;
    pt(db x=0,db y=0):x(x),y(y){} 
}p[N],q[N]; 
typedef  pt vc; 

vc operator + (vc A,vc B) { return vc(A.x+B.x,A.y+B.y);}
vc operator - (vc A,vc B) { return vc(A.x-B.x,A.y-B.y);}
bool operator <(const vc&A,const vc&B) { return A.x<B.x||(A.x==B.x&&A.y<B.y);}
int dcmp(double x) { if(fabs(x)<eps) return 0; else return x<0?-1:1;}
bool operator == (const vc&A,const vc&B) { return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0; }

db dot(vc A,vc B) { return A.x*B.x+A.y*B.y; }
db length(vc A) { return dot(A,A); }
db cross(vc A,vc B) { return A.x*B.y-A.y*B.x; }

bool cmp(const pt &A,const pt&B) {
    return dcmp(cross(A-p[1],B-p[1]))==0?length(A-p[1])<length(B-p[1]):cross(A-p[1],B-p[1])>0;
}

int top;
void graham() {
    for(int i=2;i<=n;i++) if(p[i]<p[1]) swap(p[i],p[1]);
    sort(p+2,p+n+1,cmp);
    q[++top]=p[1]; q[++top]=p[2];
    for(int i=3;i<=n;i++) {
        while(top>1&&cross(q[top]-q[top-1],p[i]-q[top-1])<eps) top--;
        q[++top]=p[i];
    }
}

db RC() {
    q[top+1]=q[1];
    int now=2; 
    db res=0;
    for(int i=1;i<=top;i++) {
        while(cross(q[i+1]-q[i],q[now]-q[i])<cross(q[i+1]-q[i],q[now+1]-q[i])) {
            now++; if(now==top+1) now=1;
        }    
        res=max(res,length(q[now]-q[i]));
    }
    return res;
}

int main() {
    read(n);
    for(int i=1;i<=n;i++) { read(p[i].x); read(p[i].y); }
    graham();
    printf("%d
",(int)RC());
    return 0;
}
凸包，旋转卡壳
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
typedef long long LL;
typedef double db;
const db eps=1e-10;
const int N=50007;
using namespace std;
int n,cnt,tot;

template<typename T>void read(T &x)  {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}

struct pt {
    db x,y;
    pt(db x=0,db y=0):x(x),y(y){} 
}p[N]; 
typedef  pt vc; 

vc operator + (vc A,vc B) { return vc(A.x+B.x,A.y+B.y);}
vc operator - (vc A,vc B) { return vc(A.x-B.x,A.y-B.y);}
vc operator * (vc A,db p) { return vc(A.x*p,A.y*p);}
vc operator / (vc A,db p) { return vc(A.x/p,A.y/p);}
bool operator <(const vc&A,const vc&B) { return A.x<B.x||(A.x==B.x&&A.y<B.y);}
int dcmp(double x) { if(fabs(x)<eps) return 0; else return x<0?-1:1;}
bool operator == (const vc&A,const vc&B) { return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0; }

db dot(vc A,vc B) { return A.x*B.x+A.y*B.y; }
db length(vc A) { return dot(A,A); }
db cross(vc A,vc B) { return A.x*B.y-A.y*B.x; }

struct ln {
    pt a,b; db slop;
    friend bool operator <(const ln&A,const ln&B) {
        return A.slop==B.slop?cross(A.b-A.a,B.b-A.a)>0:A.slop<B.slop;
    }
}L[N],a[N],que[N];

db polygonArea(int n) {
    if(n<3) return 0;
    db res=0;
    for(int i=1;i<n-1;i++)
        res+=cross(p[i]-p[0],p[i+1]-p[0]);
    return fabs(res)/2;
}

pt inter(ln A,ln B) {
    pt res;
    db s1=cross(B.b-A.a,A.b-A.a);
    db s2=cross(A.b-A.a,B.a-A.a);
    db k=s1/(s1+s2);
    res.x=B.b.x+(B.a.x-B.b.x)*k;
    res.y=B.b.y+(B.a.y-B.b.y)*k;
    return res;
}

bool ck(ln A,ln B,ln P) {
    pt pp=inter(A,B);
    return cross(P.b-P.a,pp-P.a)<0;
}

db solve() {
    sort(L+1,L+cnt+1);
    for(int i=1;i<=cnt;i++) {
        if(L[i].slop!=L[i-1].slop) tot++;
        a[tot]=L[i];
    }
    int ql=1,qr=0;
    L[++qr]=a[1]; L[++qr]=a[2];
    for(int i=3;i<=tot;i++) {
        while(qr>ql&&ck(L[qr-1],L[qr],a[i])) qr--;
        while(qr>ql&&ck(L[ql+1],L[ql],a[i])) ql++;
        L[++qr]=a[i];
    }
    while(qr>ql&&ck(L[qr-1],L[qr],L[ql])) qr--;
    while(qr>ql&&ck(L[ql+1],L[ql],L[qr])) ql++;
    L[qr+1]=L[ql];
    cnt=0;
    for(int i=ql;i<=qr;i++) 
        p[cnt++]=inter(L[i],L[i+1]);
    return polygonArea(cnt); 
}

int main() {
    read(n);
    for(int i=1;i<=n;i++) {
        int k;
        read(k);
        for(int j=1;j<=k;j++) { read(p[j].x);read(p[j].y); }
        for(int j=1;j<k;j++) {
            L[++cnt].a=p[j]; L[cnt].b=p[j+1];
        }
        L[++cnt].a=p[k]; L[cnt].b=p[1];
    }
    for(int i=1;i<=cnt;i++) 
        L[i].slop=atan2(L[i].b.y-L[i].a.y,L[i].b.x-L[i].a.x);
    printf("%.3lf
",solve());
    return 0;
}
/*
2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0
*/
半平面交
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
const int N=507;
typedef long long LL;
typedef double db;
using namespace std;
const db eps=1e-10;
int n; db r;

template<typename T>void read(T &x)  {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}

struct pt {
    db x,y;
    pt(){}
    pt(db x,db y):x(x),y(y){}
}p[N],c;

pt operator + (pt A,pt B) { return pt(A.x+B.x,A.y+B.y); }
pt operator - (pt A,pt B) { return pt(A.x-B.x,A.y-B.y); }
db dot(pt A,pt B) { return A.x*B.x+A.y*B.y; }
db length(pt A) { return sqrt(dot(A,A)); }
int dcmp(db x) { if(fabs(x)<eps) return 0; return x>0?1:-1; }

pt circle_center(pt a,pt b,pt c) {
    pt res;
    db a1=b.x-a.x,a2=c.x-a.x;
    db b1=b.y-a.y,b2=c.y-a.y;
    db c1=(a1*a1+b1*b1)/2.0;
    db c2=(a2*a2+b2*b2)/2.0;
    db d=a1*b2-a2*b1;
    res.x=a.x+(b2*c1-b1*c2)/d;
    res.y=a.y+(a1*c2-a2*c1)/d;
    return res;
}

void min_circle_cover(pt p[],int n,pt &c,db &r) {
    random_shuffle(p+1,p+n+1);
    c=p[0]; r=0;
    for(int i=2;i<=n;i++) {
        if(dcmp(length(p[i]-c)-r)>0) {
            c=p[i]; r=0;
            for(int j=1;j<i;j++) {
                if(dcmp(length(p[j]-c)-r)>0) {
                    c.x=(p[i].x+p[j].x)/2;
                    c.y=(p[i].y+p[j].y)/2;
                    r=length(p[i]-c); 
                    for(int k=1;k<j;k++) {
                        if(dcmp(length(p[k]-c)-r)>0) {
                            c=circle_center(p[i],p[j],p[k]);
                            r=length(p[k]-c);
                        } 
                    }
                }
            }
        }
    }
}

int main() {
    srand(998244353);
    for(;;) {
        read(n);
        if(!n) break;
        for(int i=1;i<=n;i++) 
            scanf("%lf %lf",&p[i].x,&p[i].y);
        min_circle_cover(p,n,c,r);
        printf("%.2lf %.2lf %.2lf
",c.x,c.y,r);
    }
    return 0;
}
最小圆覆盖
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Achenchen/p/8462427.html