#include <stdio.h>

#include <algorithm>

struct PT { int x,y; };

PT pin[128],ch[128],t[128];

int cross(const PT &p0,const PT &p1,const PT &p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

int dissqr(const PT &p1,const PT &p2)
{
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

bool cmp(const PT &p1,const PT &p2)
{
    return p1.y<p2.y||p1.y==p2.y&&p1.x<p2.x;
}

bool polarcmp(const PT &p1,const PT &p2)
{
    int u=cross(t[0],p1,p2);
    return u>0||u==0&&dissqr(t[0],p1)>dissqr(t[0],p2);
}

int area(int n)
{
    int temp=0;
    for(int i=1;i<n-1;i++)
        temp+=cross(ch[0],ch[i],ch[i+1]);
    return temp;
}

int convex(const PT *p,int n)
{
    memcpy(t,p,n*sizeof(PT));
    std::sort(t+1,t+n,polarcmp);
    if(cross(t[0],t[1],t[n-1])==0) return 0;
    ch[0]=t[0];
    int a=0;
    for(int i=1;i<n;i++)
    {
        ch[1]=t[i];
        int m=2;
        int j=i+1;
        while(cross(ch[0],ch[1],t[j])==0) j++;
        for(;j<n;j++)
            if(cross(ch[m-2],ch[m-1],t[j])>=0)  ch[m++]=t[j];
        int temp=area(m);
        if(temp>a) a=temp;
    }
    return a;
}

double sol(int n)
{
    std::sort(pin,pin+n,cmp);
    int a=0,tt;
    for(int k=0;k<n-2;k++)
        if(a<(tt=convex(pin+k,n-k))) a=tt;
    return double(a)/2;
}

int main()
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d%d",&pin[i].x,&pin[i].y);
        printf("%.1lf\n",sol(n));
    }
    return 0;
}

• Re:不知道错哪了，望牛人指点 (1772) cedar_whu 2005-09-15 07:40:40
• 感觉这个想法好像太简单了，而事情没有这么简单 (1750) frkstyc 2005-09-15 07:46:04
  • Re:我的思路 (94) Gary0_0 2005-09-15 21:58:00