欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计算几何 模板

程序员文章站 2024-01-14 17:44:04
...

凸包

POJ 1113

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;

const double eps = 1e-9;
const double PI = acos(-1.0);

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

struct vec {
    double x, y;
    vec() {x = y = 0;}
    vec(double _x, double _y): x(_x), y(_y) {}

    vec operator + (vec v) { return vec(x + v.x, y + v.y);}
    vec operator - (vec v) { return vec(x - v.x, y - v.y);}
    vec operator * (double v) {return vec(x * v, y * v);}
    vec operator / (double v) {return vec(x / v, y / v);}

    double operator * (vec v) {return x * v.x + y * v.y;}
    double len() {return hypot(x, y);}
    double lensqr() {return x * x + y * y;}
} V[1005], Z[1005];

double cross(vec a, vec b) {
    return a.x * b.y - a.y * b.x;
}

double dist(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool cmpXY(vec a, vec b) {
    if (sgn(a.x - b.x)) return a.x < b.x;
    return a.y < b.y;
}

double convex_hull(vec* v, int n, vec *z) {
    sort(v, v + n, cmpXY);
    int m = 0;
    for (int i = 0; i < n; i++) {
        while (m > 1 && cross(z[m - 1] - z[m - 2], v[i] - z[m - 2]) <= 0) --m;
        z[m++] = v[i];
    }
    int k = m;
    for (int i = n - 2; i >= 0; i--) {
        while (m > k && cross(z[m - 1] - z[m - 2], v[i] - z[m - 2]) <= 0) --m;
        z[m++] = v[i];
    }
    if (n > 1) --m;
    double ret = 0;
    for (int i = 0; i < m; i++)
        ret += dist(z[i].x, z[i].y, z[(i + 1) % m].x, z[(i + 1) % m].y);
    return ret;
}

int main() {
    //freopen("in.txt","r",stdin);
    int n;
    double r;
    while (~scanf("%d", &n)) {
        scanf("%lf", &r);
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &V[i].x, &V[i].y);
        double ret = convex_hull(V, n, Z);
        ret += PI * r * 2.0;
        int ans = ret + 0.5;
        printf("%d\n", ans);
    }
    return 0;
}

BZOJ 1185

#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#define eps 1e-8
#define inf 1000000000
using namespace std;
double ans=1e60;
int n,top;
struct P{
    double x,y;
    P(){}
    P(double _x,double _y):x(_x),y(_y){}
    friend bool operator<(P a,P b){
        return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;
    }
    friend bool operator==(P a,P b){
        return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
    }
    friend bool operator!=(P a,P b){
        return !(a==b);
    }
    friend P operator+(P a,P b){
        return P(a.x+b.x,a.y+b.y);
    }
    friend P operator-(P a,P b){
        return P(a.x-b.x,a.y-b.y);
    }
    friend double operator*(P a,P b){
        return a.x*b.y-a.y*b.x;
    }
    friend P operator*(P a,double b){
        return P(a.x*b,a.y*b);
    }
    friend double operator/(P a,P b){
        return a.x*b.x+a.y*b.y;
    }
    friend double dis(P a){
        return sqrt(a.x*a.x+a.y*a.y);
    }
}p[50005],q[50005],t[5];
bool cmp(P a,P b)
{
    double t=(a-p[1])*(b-p[1]);
    if(fabs(t)<eps)return dis(p[1]-a)-dis(p[1]-b)<0;
    return t>0;
}
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];
    for(int i=2;i<=n;i++)
    {
        while(top>1&&(q[top]-q[top-1])*(p[i]-q[top])<eps)top--;
        q[++top]=p[i];
    }
    q[0]=q[top];
}
void RC()
{
    int l=1,r=1,p=1;
    double L,R,D,H;
    for(int i=0;i<top;i++)
    {
        D=dis(q[i]-q[i+1]);
        while((q[i+1]-q[i])*(q[p+1]-q[i])-(q[i+1]-q[i])*(q[p]-q[i])>-eps)p=(p+1)%top;
        while((q[i+1]-q[i])/(q[r+1]-q[i])-(q[i+1]-q[i])/(q[r]-q[i])>-eps)r=(r+1)%top;
        if(i==0)l=r;
        while((q[i+1]-q[i])/(q[l+1]-q[i])-(q[i+1]-q[i])/(q[l]-q[i])<eps)l=(l+1)%top;
        L=(q[i+1]-q[i])/(q[l]-q[i])/D,R=(q[i+1]-q[i])/(q[r]-q[i])/D;
        H=(q[i+1]-q[i])*(q[p]-q[i])/D;
        if(H<0)H=-H;
        double tmp=(R-L)*H;
        if(tmp<ans)
        {
            ans=tmp;
            t[0]=q[i]+(q[i+1]-q[i])*(R/D);
            t[1]=t[0]+(q[r]-t[0])*(H/dis(t[0]-q[r]));
            t[2]=t[1]-(t[0]-q[i])*((R-L)/dis(q[i]-t[0]));
            t[3]=t[2]-(t[1]-t[0]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    graham();
    RC();
    printf("%.5lf\n",ans);
    int fir=0;
    for(int i=1;i<=3;i++)
        if(t[i]<t[fir])
            fir=i;
    for(int i=0;i<=3;i++)
        printf("%.5lf %.5lf\n",t[(i+fir)%4].x,t[(i+fir)%4].y);
    return 0;
}

最大空凸包

POJ 1259 HDU 6219

dp[i][j]表示以<i,j>为以o为原点选的最后一个三角形的边。(i>j)
需要确定三角形内无点
那么dp[i][j]=dp[j][k]+S(i,j,o)。需要<j,i>与<k,j>形成凸边。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;

const double eps = 1e-9;
const double PI = acos(-1.0);
const int maxn = 405;
double dp[maxn][maxn];
int T,n;

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

struct vec {
    double x, y;
    vec() {x = y = 0;}
    vec(double _x, double _y): x(_x), y(_y) {}

    vec operator + (vec v) { return vec(x + v.x, y + v.y);}
    vec operator - (vec v) { return vec(x - v.x, y - v.y);}
    vec operator * (double v) {return vec(x * v, y * v);}
    vec operator / (double v) {return vec(x / v, y / v);}

    double operator * (vec v) {return x * v.x + y * v.y;}
    double len() {return hypot(x, y);}
    double lensqr() {return x * x + y * y;}
} V[maxn], Z[maxn],o;

double cross(vec a, vec b) {
    return a.x * b.y - a.y * b.x;
}

double dist(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool cmpangle(vec a,vec b){
    int k=sgn(cross(a-o,b-o));
    if(k==0){
        return (a-o).lensqr()<(b-o).lensqr();
        //return dist(a.x,a.y,o.x,o.y)<dist(b.x,b.y,o.x,o.y);
    } else return k>0;
}

double calc_empty_convex(vec Z[],int n){
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            dp[i][j]=0;
    double ret=0;
    int j,k;
    for(int i=0;i<n;i++){
        j=i-1;
        while(j>=0 && sgn(cross(Z[i]-o,Z[j]-o))==0) j--;
        bool flg=(j==i-1);
        while(j>=0){
            k=j-1;
            while(k>=0&&cross(Z[i]-Z[j],Z[j]-Z[k])>0) k--;
            double area=fabs(cross(Z[i]-o,Z[j]-o))*0.5;
            if(k>=0) area+=dp[j][k];
            // cout<<area<<endl;
            if(flg) dp[i][j]=area;
            ret=max(area,ret);
            j=k;
        }
        if(flg){
            for(int c=1;c<i;c++)
                dp[i][c]=max(dp[i][c],dp[i][c-1]);
        }
    }
    //cout<<ret<<endl;
    return ret;
}

double empty_convex(vec V[],int n){
    double ret=0;
    for(int i=0;i<n;i++){
        o=V[i];
        int top=0;
        for(int j=0;j<n;j++)
            if(V[j].y>o.y||(sgn(V[j].y-o.y)==0&&sgn(V[j].x-o.x)>=0)){
                Z[top++]=V[j];
            }
        sort(Z,Z+top,cmpangle);
        ret=max(ret,calc_empty_convex(Z,top));
    }
    return ret;
}

int main() {
    //freopen("in.txt","r",stdin);
    cin>>T;
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&V[i].x,&V[i].y);
        double res = empty_convex(V,n);
        printf("%.1f\n",res);
    }
    return 0;
}