HDU 1348 Wall

题解：计算凸包周长
#include <iostream>

#include <cmath>

#include <algorithm>

const int size=1000;

using namespace std;

struct pint{int x,y;}x[size];

int n,l,ans[size],cnt,sta[size],tail;

bool cmp(pint a,pint b){return (a.y1 && !crossleft(x[sta[tail-1]],x[sta[tail-2]],x[i]))

            tail--;

        sta[tail++]=i;

    }

    for(int i=0;i<tail;i++)

        ans[cnt++]=sta[i];

    tail=0;

    sta[tail++]=n-1;

    sta[tail++]=n-2;

    for(int i=n-3 ;i>=0;i--){

        while(tail>1 && !crossleft(x[sta[tail-1]],x[sta[tail-2]],x[i]))

            tail--;

        sta[tail++]=i;

    }

    for(int i=0;i<tail;i++)

        ans[cnt++]=sta[i];

}

int main(){

    int tt;

    while(scanf("%d",&tt)!=EOF){

        while(tt--){

            scanf("%d%d",&n,&l);

                for(int i=0;i<n;i++)

                    scanf("%d%d",&x[i].x,&x[i].y);

                jarvis();

                double re=4*acos(0.0)*l;

                for(int i=0;i<cnt-1;i++)

                    re+=sqrt((x[ans[i]].x-x[ans[i+1]].x)*(x[ans[i]].x-x[ans[i+1]].x)*1.0

                            +(x[ans[i]].y-x[ans[i+1]].y)*(x[ans[i]].y-x[ans[i+1]].y)*1.0);

                printf("%.0lf\n",re);

                if(tt)

                printf("\n");

        }

    }

    return 0;

}
巴特西

HDU 1348 Wall

最新文章

热门文章
