「NOIP模拟赛」超电磁炮

2014年6月27日1,5930

「题目描述」

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

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

 

说点什么

提醒
avatar