2242.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2242 on 2006-05-22 at 19:45:54 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int PN = 512;
const int DIR[][3] = { { 1, 2, 0 }, { 0, 2, 1 }, { 0, 1, 2 } };

int a[3];

class Point {
public:
	int x[3], d[3];
	void make() { scanf("%d %d %d", &x[0], &x[1], &x[2]); }
	bool operator <(const Point&) const;
	bool line(const Point&) const;
};
bool Point::operator <(const Point& p) const {
	int i;
	for(i = 0; i < 3; i++)
		if(x[a[i]] != p.x[a[i]]) return x[a[i]] < p.x[a[i]];
	return false;
}
bool Point::line(const Point& p) const {
	int i;
	for(i = 0; i < 2; i++)
		if(x[a[i]] != p.x[a[i]]) return false;
	return true;
}

int main()
{
	int n, i, j;
	Point p[PN];
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) p[i].make();
		for(i = 0; i < 3; i++) {
			memcpy(a, DIR[i], sizeof(a));
			sort(p, p+n);
			int b = 0, e;
			for(e = 1; e <= n; e++)
				if(e == n || !p[e].line(p[e-1])) {
					for(j = b; j != e; j++) p[j].d[i] = max(j-b, e-j-1);
					b = e;
				}
		}
		int sn = 0;
		do {
			sort(p, p+n);
			for(i = 0; i < n; i++)
				for(j = i+1; j < n; j++)
					if(!p[i].line(p[j])) break;
					else if(p[i].d[a[0]] == 0 || p[j].d[a[1]] == 0) continue;
					else sn = max(sn, p[i].d[a[0]]+p[j].d[a[1]]+j-i+1);
		} while(next_permutation(a, a+3));
		printf("%d\n", sn);
	}
	
	return 0;
}