1886.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1886 on 2006-09-04 at 01:34:04 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1024;
const double eps = 1e-12;

class Point {
public:
	int x, y, hyd;
	void make() { scanf("%d %d %d", &x, &y, &hyd); }
};

class Dir {
public:
	int wn, an;
	double ang;
	void make(const Point&, const Point&, int);
	bool operator <(const Dir& d) const { return ang+eps < d.ang; }
};
void Dir::make(const Point& a, const Point& b, int o) {
	wn = an = 0;
	ang = atan2(1.0*b.x-a.x, 1.0*b.y-a.y);
	if(b.hyd) wn++;
	else an++;
}

int main()
{
	int n;
	Point p[N];
	Dir d[N];

	while(scanf("%d", &n) != EOF && n != 0) {
		for(int i = 0; i < n; i++) p[i].make();
		if(n <= 3) { printf("%d\n", n); continue; }
		int best = 0, tk = n-1, m;
		for(int i = 0; i < n; i++) {
			int wt = 0, ace = 0, tw = 0, ta = 0;
			for(int j = 0, k = 0; j < n; j++) {
				if(j == i) continue;
				d[k++].make(p[i], p[j], j);
				if(p[j].hyd) tw++;
				else ta++;
			}
			sort(d, d+tk);
			for(int i = m = 1; i < tk; i++)
				if(fabs(d[i].ang-d[i-1].ang) < eps) { d[m-1].wn += d[i].wn; d[m-1].an += d[i].an; }
				else d[m++] = d[i];
			double dif, ex = 0;
			for(int b = 0, e = 0; b < m; b++) {
				int lw = 0, la = 0, ext = 1+d[b].wn+d[b].an;
				wt -= d[b].wn; lw += d[b].wn; ace -= d[b].an; la += d[b].an;
				while(true) {
					dif = d[e].ang-d[b].ang;
					if(dif+ex+eps > M_PI) break;
					wt += d[e].wn; ace += d[e].an;
					e = (e+1)%m;
					if(e == 0) ex = 2*M_PI;
				}
				if(fabs(dif-M_PI) < eps) { ext += d[e].wn+d[e].an; lw += d[e].wn; la += d[e].an; }
				best >?= max(wt+ta-la-ace, ace+tw-lw-wt)+ext;
			}
		}
		printf("%d\n", best);
	}
	
	return 0;
}