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