1259.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"fstream.h"
#include"stdio.h"
#include"math.h"
#include<vector>
#include<algorithm>
//#include"time.h"

using namespace std;
long area[100][100],best;

struct point
{long x,y;
};
vector<point> p;
int n;
inline long cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}

inline long dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}

point o;
int cmp2(point a,point b)
{return cheng(o,a,b)>0||(cheng(o,a,b)==0&&dcheng(a,o,b)<0);}


long doit(point *pt,int n)
{int i,j,k,h,set;long s,t;

point p[101];
o=pt[0];n--;
for(i=0;i<n;i++)p[i]=pt[i+1];
sort(&p[0],&p[n],cmp2);
s=0;
for(i=1;i<n;i++)s+=cheng(o,p[i-1],p[i]);
if(s<best)return 0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
area[i][j]=0;

s=0;
for(i=1;i<n;i++)
{j=i-1;
while(j>=0&&cheng(o,p[i],p[j])==0)j--;

if(j!=i-1)set=1;else set=0;
for(h=j;j>=0;j--)
{if(cheng(p[i],p[h],p[j])>0)continue;
	else 
	{t=0;
	for(k=j-1;k>=0;k--)
	{if(cheng(p[i],p[k],p[j])>=0&&t<area[j][k])
	t=area[j][k];}
	
	area[i][j]=t+cheng(o,p[j],p[i]);
	if(area[i][j]>s)
	s=area[i][j];
	if(set)area[i][j]=0;
	h=j;
	}
}
}
return s;
}
int cmp(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}


int main()
{//long time=clock();
	int i,t;long tt;
cin>>t;
while(t--)
{cin>>n;p.resize(n);
for(i=0;i<n;i++)cin>>p[i].x>>p[i].y;
sort(p.begin(),p.end(),cmp);
best=0;
for(i=0;i<n-2;i++)
{tt=doit(&p[i],n-i);
if(tt>best)best=tt;
}
printf("%.1f\n",(float)best/2);
}
//printf("time : %d",time-clock());
return 0;
}