2428.txt

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

#include"iostream.h"
#include"stdio.h"
#include"math.h"


struct point
{
	double x,y,z;
}p1[110],p2[110],p3[110];
int n,m;
double best[110][110];

double cross(point a,point b,point c)
{
	b.x-=a.x;b.y-=a.y;b.z-=a.z;
	c.x-=a.x;c.y-=a.y;c.z-=a.z;

	double s1,s2,s3;
	s1=b.y*c.z-b.z*c.y;
	s2=b.z*c.x-b.x*c.z;
	s3=b.x*c.y-b.y*c.x;
	return sqrt(s1*s1+s2*s2+s3*s3);
}

int init(void)
{
	int i;double s1,s2;
	cin>>n;
	if(cin.fail())return 0;
	
	for(i=0;i<n;i++)
	{
		cin>>p1[i].x>>p1[i].y;
		p1[i].z=0;
	}
	p1[n]=p1[0];
        s1=0;
	for(i=0;i<n;i++)
        s1+=p1[i].x*p1[i+1].y-p1[i].y*p1[i+1].x;

	cin>>m;
	for(i=0;i<m;i++)
	{
		cin>>p2[i].x>>p2[i].y;
		p2[i].z=10;
	}
	
	p2[m]=p2[0];
	s2=0;
	
	for(i=0;i<m;i++)
	s2+=p2[i].x*p2[i+1].y-p2[i].y*p2[i+1].x;
	
	if(s1*s2<0)
	{
		for(i=0;i<=m;i++)
		p3[i]=p2[m-i];
		for(i=0;i<=m;i++)
		p2[i]=p3[i];
     }

	return 1;
}
double answer;
void doit()
{
	int i,j,k;
	double temp,t;
	answer=1e100;

	for(i=0;i<m;i++)
	{
		for(j=0;j<=m;j++)
			p3[j]=p2[(j+i)%m];
		
		for(j=0;j<=n;j++)
		for(k=0;k<=m;k++)
			best[j][k]=1e100;

		best[0][0]=0;

		for(j=0;j<=n;j++)
		for(k=0;k<=m;k++)
		{
	//		temp=1e+100;
			
//			if(k!=0)
			{
				t=best[j][k]+cross(p3[k+1],p1[j],p3[k]);
				if(t<best[j][k+1])
					best[j][k+1]=t;
			}
//			if(j!=0)
			{
				t=best[j][k]+cross(p3[k],p1[j],p1[j+1]);
				if(t<best[j+1][k])
					best[j+1][k]=t;
			}
			
		}

		if(answer>best[n][m])
			answer=best[n][m];
	}
	printf("%.0lf\n",answer/2);
}

int main()
{
	while(init())
		doit();
	return 0;
}