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