> 
> #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:我的思路 (94) Gary0_0 2005-09-15 21:58:00