2235.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2235 on 2006-05-17 at 08:07:10 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int PN = 1024;

class Point {
public:
	int x, y;
	void make() { scanf("%d %d", &x, &y); }
	void make(const Point&, const Point&);
	bool operator <(const Point& p) const { return p.x*y < p.y*x; }
};
void Point::make(const Point& a, const Point& b) {
	x = a.x-b.x; y = a.y-b.y;
	if(x < 0) { x = -x; y = -y; }
	else if(x == 0) y = abs(y);
}

int main()
{
	Point p[PN], sub[PN];
	int n, i, j, t;

	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		for(i = 0; i < n; i++) p[i].make();
		int best = 0;
		for(i = 0; i < n; i++) {
			for(j = i+1; j < n; j++) sub[j-i-1].make(p[i], p[j]);
			int m = n-i-1, line = 0, lm = 0;
			sort(sub, sub+m);
			for(j = 0; j < m; j++)
				if(j == 0 || sub[j-1] < sub[j]) line = 1;
				else { line++; lm = max(lm, line); }
			best = max(best, lm+1);
			if(best >= m) break;
		}
		printf("Photo %d: %d points eliminated\n", t, best < 4 ? 0 : best);
	}
	
	return 0;
}