【NOIP模拟赛】超电磁炮

2014年6月27日1,2060

【题目描述】

早苗入手了最新的超电磁炮。最新款自然有着与以往不同的功能,那就是它的轨迹是条直线,厉害吧。

2维平面上有n个目标,任意2个目标的坐标不会相同。超电磁炮的威力强到穿透一切,那么早苗一枪最多能击中多少目标?

 

【输入格式】

第1行:一个整数n,表示目标数量。

第2-n+1行:每行有两个整数xi和yi(-2 000 000 000≤xi,yi≤2 000 000 000),表示第i个教徒在地图中的行、列坐标。

 

【输出格式】

一个整数表示答案。

 

【样例输入】

5

0 0

1 1

2 2

0 3

2 3

【样例输出】

3

【数据范围】

对于40%的数据 N<=200;

对于100%的数据 N<=1500;

 

选定每个点为基点,极角排序然后扫一遍

复杂度n^2logn