2066.txt

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

#include"iostream.h"
#include"stdio.h"
#include"math.h"
#include"algorithm"
using namespace std;
/////////////////////////
#define Type long /*坐标类型*/
/////////////////////////
inline long max(long a,long b)
{
	return a>b?a:b;
}
struct point
{
	Type x,y;
}p[100];
struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),b(y)
{;}
};

inline Type 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 Type cheng(point b,point c)
{
	return b.x*c.y-c.x*b.y;
}
inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}

int jiao(line l1,line l2)
{
double s1=cheng(l1.a,l1.b,l2.a),
s2=cheng(l1.a,l1.b,l2.b),s3,s4;
if(s1*s2>0)return 0
s3=cheng(l2.a,l2.b,l1.a);s4=cheng(l2.a,l2.b,l1.b);
if(s3*s4>0)return 0;
if(s1*s2<0&&s3*s4<0)return 1;
if( dcheng(l1.a,l2.a,l2.b)<=0
||dcheng(l1.b,l2.a,l2.b)<=0
||dcheng(l2.a,l1.a,l1.b)<=0
||dcheng(l2.b,l1.a,l1.b)<=0)
return 2;
return 0;
}
long area[50][50];
int n;
int main()
{
	int t,i,j,l,k;long s;
	cin>>t;		
	while(t--)
	{
		cin>>n;		
		s=0;
		for(i=0;i<n;i++)
		{
			cin>>p[i].x>>p[i].y;
			if(i)
				s+=cheng(p[i-1],p[i]);
		}
		s+=cheng(p[n-1],p[0]);
		if(s<0)
		for(i=0;i<n/2;i++)
			swap(p[i],p[n-1-i]);
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			area[i][j]=0;
		for(l=2;l<n;l++)
		for(i=0;i<n-l;i++)
		{
			k=i+l;area[i][k]=-1;			
			//if(cheng(p[i+1],p[k],p[i])<0)continue;			
			for(j=i+2;j<k;j++)
			{
				if(jiao(line(p[k],p[i]),line(p[j],p[j-1])))break;
			}
			if(j<k)continue;
			//if(cheng(p[(k+1)%n],p[k],p[i])>0)continue;			
			for(j=k+2;j<i+n;j++)
			{
				if(jiao(line(p[k],p[i]),line(p[j%n],p[(j-1)%n])))break;
			}
			if(j<i+n)continue;						
			for(j=i+1;j<k;j++)
			{
				if(area[i][j]<0||area[j][k]<0)continue;
				s=max( max(cheng(p[j],p[k],p[i]),area[i][j]),area[j][k]);

				if(s<area[i][k]||area[i][k]==-1)area[i][k]=s;
			}
		}

		printf("%.1lf\n",(double)area[0][n-1]/2);
	}

	return 0;
}