# Poj Solution 2280

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

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

double const pi=3.1415926535898;

struct point
{
double x,y;
int r;
enum {up,down}side;
double th;
}p[1010],ptemp[1010];

int n;

//degree
//from n-1 to j

double theta(int j)
{
return atan2(p[j].y-p[n-1].y,p[j].x-p[n-1].x);
}
bool cmp(point a,point b)
{
return a.th<b.th;
}
////
void sortit(int k)
{
int i;
swap(p[k],p[n-1]);

for(i=0;i<n-1;i++)
{
p[i].th=theta(i);

if(p[i].th==pi)
p[i].th=0,    p[i].side=point::down;
else if(p[i].th<0)
p[i].th=pi+p[i].th,    p[i].side=point::down;
else p[i].side=point::up;
}

sort(p,p+n-1,cmp);
}
//
int count(int &up_0,int &up_1,int &down_0,int &down_1,int &on)
{
on=1;up_0=up_1=down_0=down_1=0;

int i=0,ii;
for(;i<n-1&&p[i].th==0;i++)
on++;
ii=i;

for(;i<n-1;i++)
if(p[i].r==1)
{
if(p[i].side==point::up)up_1++;
else down_1++;
}
else
{
if(p[i].side==point::up)up_0++;
else down_0++;
}
return ii;
}

//k>kk
int rotate(int k,int kk,int &up_0,int &up_1,int &down_0,int &down_1,int &on)
{
double dgree=p[k].th;

int i;
for(i=kk;i<k;i++)
{
on--;
if(p[i].r==1)
{
if(p[i].side==point::up)down_1++;
else up_1++;
}
else
{
if(p[i].side==point::up)down_0++;
else up_0++;
}
}

for(;i<n-1&&fabs(p[i].th-dgree)<1e-8;i++)
{
on++;
if(p[i].r==1)
{
if(p[i].side==point::up)up_1--;
else down_1--;
}
else
{
if(p[i].side==point::up)up_0--;
else down_0--;
}
}
return i;
}

void init()
{
for(int i=0;i<n;i++)
cin>>ptemp[i].x>>ptemp[i].y>>ptemp[i].r;
return;
}

int doit()
{
int best=0,i,k,kk,t;
int up_0,up_1,down_0,down_1,on;

for(i=0;i<n;i++)
{
copy(ptemp,ptemp+n,p);
sortit(i);
k=count(up_0,up_1,down_0,down_1,on);

if(best<up_0+down_1+on)best=up_0+down_1+on;
if(best<up_1+down_0+on)best=up_1+down_0+on;

kk=0;

for(;k<n-1;)
{
t=rotate(k,kk,up_0,up_1,down_0,down_1,on);
kk=k;
k=t;
if(best<up_1+down_0+on)best=up_1+down_0+on;
if(best<up_0+down_1+on)best=up_0+down_1+on;
}
}

return best;
}

int main()
{
while(1)
{
cin>>n;
if(n==0)break;
init();
cout<<doit()<<endl;
}
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.