pku1118.cpp

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

#include <stdio.h>
#include <stdlib.h>

typedef struct 
{
	int x, y;
}Point;

Point p[1001], d[1001];
int N;

int Abs(int x)
{
	return (x > 0) ? x : -x;
}

int sgn(int x)
{
	if (x > 0)
	{
		return 1;
	}
	else if (x == 0)
	{
		return 0;
	}
	else
	{
		return -1;
	}
}

int det(Point *aa, Point *bb)
{
	return aa->x * bb->y - bb->x * aa->y;
}

int cp(const void *a, const void *b)
{
	Point *aa = (Point *)a;
	Point *bb = (Point *)b;
	return det(aa, bb);
}

int main()
{
	int i, j, max, tmax, cnt;
	while (scanf("%d", &N) != -1 && N > 0)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d %d", &p[i].x, &p[i].y);
		}
		if (N <= 2)
		{
			printf("%d\n", N);
			continue;
		}
		for (i = 0, max = 2; i < N; i++)
		{
			for (j = 0, tmax = 2; j < N; j++)
			{
				if (i == j)
				{
					continue;
				}
				else if (p[i].x == p[j].x)
				{
					d[j].x = 0;
					d[j].y = 1;
				}
				else if (p[i].y == p[j].y)
				{
					d[j].x = 1;
					d[j].y = 0;
				}
				else
				{
					d[j].x = Abs(p[i].x - p[j].x);
					d[j].y = sgn(p[i].x - p[j].x) * (p[i].y - p[j].y);
				}
			}
			d[i].x = d[0].x;
			d[i].y = d[0].y;
			qsort(d + 1, N - 1, sizeof(d[0]), cp);
			for (j = 1, cnt = 2; j < N - 1; j++)
			{
				if (det(d + j, d + j + 1) == 0)
				{
					cnt++;
				}
				else
				{
					if (tmax < cnt)
					{
						tmax = cnt;
					}
					cnt = 2;
				}
			}
			if (cnt > tmax)
			{
				tmax = cnt;
			}
			if (tmax > max)
			{
				max = tmax;
			}
		}
		printf("%d\n", max);
	}
	return 0;
}