2280.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"algorithm"
#include"math.h"
#include"iostream.h"
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;
}