POJ_1118 Lining Up

問題
座標が整数の点がN個(1解法
点を2個決め、その２点を通る直線は何個の点を通るか調べていけばいい。

3点 p1(x1,y1), p2(x2,y2), p3(x3,y3)が一直線上にある時、次の式が成立する。
(x2 - x1) * (y3 - y1) = (x3 - x1) * (y2 - y1)
[証明]
p1,p2を通る直線と、p1,p3を通る直線の傾きが等しいなら、3点は一直線上にあるから、
(x2 - x1) / (y2 - y1) = (x3 - x1) / (y3 - y1)
両辺に(y2-y1)(y3-y1)をかけて
(x2 - x1) * (y3 - y1) = (x3 - x1) * (y2 - y1)
実装

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 700;
int n;
int px[MAX_N];
int py[MAX_N];

bool on(int x1, int y1, int x2, int y2, int x3, int y3){
	return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1);
}
int main(){
	while(scanf("%d", &n) && n){
		for(int i = 0; i < n; i++)
			scanf("%d %d", &px[i], &py[i]);
		int ans = 0;
		for(int i = 0; i < n; i++){
			for(int j = i + 1; j < n; j++){
				int res = 0;
				for(int k = 0; k < n; k++){
					if(on(px[i], py[i], px[j], py[j], px[k], py[k])){
						res++;
					}
				}
				ans = max(ans, res);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}