# Poj Solution 2428

```http://poj.org/problem?id=2428

#include<iostream>
#include"stdio.h"
#include"math.h"
using namespace std;

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

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;
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;
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;
}
void doit()
{
int i,j,k;
double temp,t;

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;

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;
}

}