hdu 1392 Surround the Trees

凸包模板

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;


const int N=105;
const double eps=1e-8;


struct point{
    double x;
    double y;
}p[N], stack[N];


bool isZero(double x){
    return (x>0 ? x : -x) <eps;
}


double dis(point A,point B){
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}


double crossProd(point A,point B,point C){
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}




int cmp(const void *a, const void *b) {
    point *c = (point *)a;
    point *d = (point *)b;
    double k = crossProd(p[0], *c, *d);//极角大小转化为求叉乘
    if (k<eps || isZero(k) && dis(p[0], *c)>dis(p[0], *d)) return 1;
    return -1;
}


double Graham(int n)
{
    int i,x=p[0].x,y=p[0].y;
    int mi=0;
    for( i=1;i<n;i++){
        if(p[i].x<x||(p[i].x==x&&p[i].y<y)){
            x=p[i].x;
            y=p[i].y;
            mi=i;
        }
    }
    point tmp=p[mi];
    p[mi]=p[0];
    p[0]=tmp;
   qsort(p+1, n-1, sizeof(point), cmp);
    p[n]=p[0];
    stack[0]=p[0];stack[1]=p[1];stack[2]=p[2];
    int top=2;
    for(i=3;i<=n;i++){
        while(crossProd(stack[top-1],stack[top],p[i])<eps &&top>=2) --top;
        stack[++top]=p[i];
    }
    double len=0;
    for(int i=0;i<top;i++) len+=dis(stack[i],stack[i+1]);
    return len;
}


int main()
{
    int n;
    while(scanf("%d",&n),n){
        int i;
        for(i=0;i<n;i++){
            scanf("%lf %lf",&p[i].x,&p[i].y);
        }
        if(n==1) printf("0.00\n");
        else if(n==2) printf("%.2lf\n",dis(p[0],p[1]));
        else
            printf("%.2lf\n",Graham(n));
    }
}

hdu 1392 Surround the Trees,布布扣,bubuko.com

hdu 1392 Surround the Trees

原文：http://blog.csdn.net/cnh294141800/article/details/21480179