g051: 最多點的線
Tags :
Accepted rate : 11人/22人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-01 22:06

Content

給你$N$個點,請你找出最多有幾個點在同一條直線上

Input

第一行一個整數$N$,代表總共有$N$個點

接下來有$N$行,每行一個點$(x_i, y_i)$,保證點不重複出現

保證最多點的那條直線上有超過 $N/4$ 個點

$2 \leq N \leq 2 * 10^5$

$-2^{31} <= x_i, y_i <= 2^{31}-1$

Output

輸出一個整數,最多有多少點在同一條直線上

Sample Input #1
10
1 1
2 2
5 123
5 922
5 1982730
5 12280
3 3
98 1111
2222 3333
4444 98
Sample Output #1
4
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (16%): 10.0s , <10M
不公開 測資點#1 (16%): 10.0s , <10M
不公開 測資點#2 (17%): 10.0s , <10M
不公開 測資點#3 (17%): 10.0s , <10M
不公開 測資點#4 (17%): 10.0s , <10M
不公開 測資點#5 (17%): 10.0s , <10M
Hint :

範例測資一中,(5, 123), (5, 922), (5, 1982730), (5, 12280)在同一條直線上(x = 5)

 

#2021/08/01新增測資5

Tags:
出處:
[管理者: fire5386(Penguin07) ]


ID User Problem Subject Hit Post Date
27632 linlincaleb@...(臨末之頌) g051
好題
296 2021-10-20 22:54
26928 fire5386(Penguin07) g051
425 2021-09-02 17:58