# 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;
}
```
This entry was posted in poj. Bookmark the permalink.