http://poj.org/problem?id=2428
#include<iostream>
#include"stdio.h"
#include"math.h"
using namespace std;
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("%.0lfn",answer/2);
}
int main()
{
while(init())
doit();
return 0;
}