POJ 3246 Game（凸包）

【题目链接】 http://poj.org/problem?id=3246

【题目大意】

　　给出一些点，请删去一个点，使得包围这些点用的线长最短

【题解】

　　去掉的点肯定是凸包上的点，所以枚举凸包上的点去掉，再计算面积即可。

【代码】

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

#include <cstring>

using namespace std;

struct P{

    int x,y;

    int id;

    P(){}

    P(double x,double y):x(x),y(y){}

    P operator + (P p){return P(x+p.x,y+p.y);}

    P operator - (P p){return P(x-p.x,y-p.y);}

    P operator * (double d){return P(x*d,y*d);}

    int dot(P p){return x*p.x+y*p.y;} //点积

    int det(P p){return x*p.y-y*p.x;}  //叉积

};

bool cmp_x(const P& p,const P& q){

    if(p.x!=q.x)return p.x<q.x;

    return p.y<q.y;

}

vector<P> convex_hull(P* ps,int n){

    sort(ps,ps+n,cmp_x);

    int k=0;

    vector<P> qs(n*2);

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

        while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;

        qs[k++]=ps[i];

    }

    for(int i=n-2,t=k;i>=0;i--){

        while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;

        qs[k++]=ps[i];

    }qs.resize(k-1);

    return qs;

}

int cross(P a, P b,P c){return(b-a).det(c-a);}

int compute_area(P A,P B,P C){

    int res=cross(A,B,C);

    if(res<0){return -res;}

    return res;

}

int compute_area(const vector<P>& ps){

    int total=0;

    for(int i=2;i<ps.size();i++){

        total+=compute_area(ps[0],ps[i-1],ps[i]);

    }return total;

}

const int MAX_N=100010;

int N;

P p[MAX_N],q[MAX_N];

void solve(){

    for(int i=0;i<N;i++){

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

        p[i].id=i;

    }memcpy(q,p,N*sizeof(P));

    vector<P> ps=convex_hull(p,N);

    int ans=0x3f3f3f3f;

    for(int i=0;i<ps.size();i++){

        memcpy(p,q,N*sizeof(P));

        swap(p[ps[i].id],p[N-1]);

        ans=min(ans,compute_area(convex_hull(p,N-1)));

    }printf("%d.%s\n",ans/2,ans%2==1?"50":"00");

}

int main(){

    while(~scanf("%d",&N),N)solve();

    return 0;

}