pku2737.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 77 行

#include <cstdio>
#include <algorithm>
#include <cmath>
#define size 1100
using namespace std;

class Point
{
	public:
	int x, y;
	double Ang(Point b)
	{
		return fabs(atan2(y - b.y, x - b.x));
	}
};

Point p[size];
double ang[size];
int N;

bool cmp(const Point &a, const Point &b)
{
	return (a.y < b.y) || (a.y == b.y && a.x < b.x);
}

bool cmp_double(const double &a, const double &b)
{
	return a < b;
}

int main()
{
	int t, i, j;
	int max, cnt;
	t = 0;
	while (EOF != scanf("%d", &N) && N)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d %d", &p[i].x, &p[i].y);
		}
		max = 2;
		sort(p, p + N, cmp);
		for (i = 0; i < N; i++)
		{
			for (j = i + 1; j < N; j++)
			{
				ang[j] = p[j].Ang(p[i]);
			}
			sort(ang + i + 1, ang + N, cmp_double);
			cnt = 2;
			for (j = i + 2; j < N; j++)
			{
				if (fabs(ang[j] - ang[j - 1]) < 1e-6)
				{
					cnt++;
				}
				else
				{
					if (cnt > max)
					{
						max = cnt;
					}
					cnt = 2;
				}
			}
			if (cnt > max)
			{
				max = cnt;
			}
		}
		printf("Photo %d: %d points eliminated\n", ++t, max > 3 ? max : 0);
	}
	return 0;
}