Bài toán hình học phẳng: cho ~N~ điểm trên mặt phẳng ~Oxy~, hãy tìm số lượng điểm lớn nhất cùng thẳng hàng (nằm trên một đường thẳng).

Yêu cầu

Đếm giá trị lớn nhất của số điểm cùng nằm trên một đường thẳng bất kỳ trong số ~N~ điểm đã cho.

Dữ liệu

• Dòng đầu: số nguyên dương ~N~ ~(1\le N\le 2\times 10^3)~.
• ~N~ dòng sau: mỗi dòng chứa hai số nguyên ~x~, ~y~ là toạ độ của một điểm với ~|x|,|y|\le 10^9~.

Kết quả

• Một số nguyên là số điểm lớn nhất cùng thuộc một đường thẳng.

Ví dụ

Ví dụ 1

Input

4
2 2
3 3
4 5
1 1

Output

3

Ví dụ 2

Input

5
0 0
1 1
2 2
3 4
-1 -1

Output

4

Giải thích

Ví dụ 1

Ba điểm ~(-)~ ~\,(1,1),(2,2),(3,3)~ cùng nằm trên đường thẳng ~y=x~, nên đáp án là ~3~.

Ví dụ 2

Bốn điểm ~(-1,-1),(0,0),(1,1),(2,2)~ thẳng hàng trên ~y=x~ nên kết quả là ~4~.

Gợi ý (Có thể đúng hoặc sai)

• 100% số điểm cho lời giải ~\mathcal{O}(N^2\log C)~ hoặc ~\mathcal{O}(N^2)~ với băm, trong đó ~C~ là miền trị tuyệt đối của toạ độ:
  • Với mỗi điểm gốc ~P_i~, chuẩn hoá hệ số góc của các vector ~\overrightarrow{P_iP_j}~ bằng cách rút gọn cặp ~\big(\Delta y,\Delta x\big)~ theo ~\gcd(|\Delta y|,|\Delta x|)~, đồng thời cố định dấu (ví dụ ép ~\Delta x>0~, hoặc nếu ~\Delta x=0~ thì đặt cặp là ~(1,0)~ cho đường thẳng đứng).
  • Tính tần suất từng hệ số góc (số điểm cùng hàng qua ~P_i~) bằng bảng băm/ map; đáp án tạm thời cho gốc ~P_i~ là ~\max\_\text{slope}\{\text{freq(slope)}\}+\text{trùng\_điểm}~, trong đó ~\text{trùng\_điểm}~ là số điểm trùng toạ độ với ~P_i~ (nếu có).
  • Lấy tối đa qua mọi ~i~. Trường hợp ~N\le 2~, đáp án bằng ~N~.
• Lưu ý chống tràn khi tính ~\Delta y~, ~\Delta x~ (dùng kiểu 64-bit), và xử lý riêng đường thẳng đứng/ ngang bằng quy tắc chuẩn hoá nêu trên.