1099.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1099 on 2005-11-01 at 22:58:20 */ 
#include <cstdio>
#include <cstdlib>

const int MAX = 720;

typedef struct {
	int x;
	int y;
} Line;

typedef struct {
	int x;
	int y;
} Point;

Line line[MAX];
Point point[MAX];

int cmp(const void*, const void*);

int main()
{
	int n, i, j, k;
	int max, p;

	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			for(i = 0; i < n; i++) {
				scanf("%d %d", &point[i].x, &point[i].y);
			}
			max = 0;
			for(i = 0; i < n; i++) {
				for(j = i+1; j < n; j++) {
					k = j - i - 1;
					line[k].x = point[i].x - point[j].x;
					line[k].y = point[i].y - point[j].y;
					if(line[k].y < 0) {
						line[k].x = -line[k].x;
						line[k].y = -line[k].y;
					} else if(line[k].y == 0) {
						line[k].x = line[k].x > 0 ? line[k].x : -line[k].x;
					}
				}
				qsort(line, n-i-1, sizeof(Line), cmp);
				p = 2;
				for(k = 1; k < n-i-1; k++) {
					if(line[k].x*line[k-1].y == line[k].y*line[k-1].x) {
						p++;
					} else {
						if(p > max) {
							max = p;
						}
						p = 2;
					}
				}
				if(p > max) {
					max = p;
				}
			}
			printf("%d\n", max);
		}
	}
	
	return 0;
}

int cmp(const void *a, const void *b)
{
	Line *x = (Line*)a, *y = (Line*)b;
	if(x->x*y->y < x->y*y->x) {
		return -1;
	} else {
		return 1;
	}
}