Poj Solution 1630

http://poj.org/problem?id=1630

#include<iostream>
using namespace std;
struct point
{int x,y;};

long cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
long dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)+(c.y-a.y);}


point p[10000];
int n,k[32],begin[32],end[32],m;

void init()
{int i,h=0;char c;
cin>>n;

for(i=0;i<=n;i++)
{begin[i]=h;
while(cin.peek()!='#')
{cin>>p[h].x>>c;
cin>>p[h++].y>>c;

}
cin.get();
end[i]=h;
}

m=h;
}

int side(int a,int b,int s,int key,int sign)
{int i,r;
for(i=begin[s];i<end[s];i++)
if(i!=a&&i!=b)
{r=cheng(p[i],p[a],p[b]);
if(r==0){if(dcheng(p[i],p[a],p[b])<0)return 0;
         if(a<end[0]&&p[i].x==p[a].x&&p[i].y==p[a].y)return 0;
         if(b<end[0]&&p[i].x==p[b].x&&p[i].y==p[b].y)return 0;
        if(a<end[0]&&b>end[0]&&dcheng(p[a],p[i],p[b])<0)return 0;
        if(b<end[0]&&a>end[0]&&dcheng(p[b],p[i],p[a])<0)return 0;
        if(dcheng(p[a],p[i],p[b])*sign>0)return 0;
        }
else if(r*key>0)return 0;
}

return 1;
}





int main()
{long key;int k,h,best,r,sign,s;
init();
int i,j;
best=0;
if(m==2){cout<<1<<endl;return 0;}

for(i=0;i<m;i++)
for(j=i+1;j<m;j++)
if(p[i].x!=p[j].x||p[i].y!=p[j].y)
{
sign=0;
key=0;

for(k=0;k<end[0];k++)
if(k!=i&&k!=j)
    {r=cheng(p[k],p[i],p[j]);
    if(r==0){if(dcheng(p[k],p[i],p[j])<=0)break;
            s=dcheng(p[i],p[k],p[j]);
            if(!sign)sign=s;
            else if(sign*s<0)break;
            }
    else {if(!key)key=r;
        else if(key*r<0)break;
        }
    }

if(k<end[0])continue;

h=0;
if(key)for(k=1;k<=n;k++)h+=side(i,j,k,key,sign);
else {key=-1;for(k=1;k<=n;k++)h+=side(i,j,k,key,sign);
    if(h>best)best=h;h=0;    
        key=1;for(k=1;k<=n;k++)h+=side(i,j,k,key,sign);}
if(h>best)best=h;
}


cout<<best<<endl;
return 0;
}