Olimpiade Sains Provinsi (OSP) 2019 - Komputer, Nomor 42

UKURAN SEGMEN

Pak Dengklek memiliki N buah titik dan ingin membentuk suatu himpunan garis penghubung dua buah titik yang valid. Sebuah himpunan garis dikatakan valid apabila semua garis di dalamnya memiliki gradien yang sama. Setiap titik dapat menjadi bagian dari satu atau lebih garis. Apabila dua buah garis tersebut berimpit, maka dua garis tersebut dihitung sebagai 2 garis yang berbeda. Karena jumlah titik sangat banyak, pak Dengklek tidak dapat menghitungnya satu-persatu. Pak Dengklek meminta bantuan kalian peserta OSP Informatika 2019 untuk membuat program yang dapat mengeluarkan ukuran maksimum garis valid!

Format Masukan:
Baris pertama berisi sebuah bilangan bulat N.
N baris berikutnya masing-masing berisi 2 bilangan bulat x_i dan y_i, menandakan koordinat titik ke-i.

Format Keluaran:
Sebuah bilangan berisi banyaknya elemen maksimum dalam semua himpunan garis valid.

Batasan:

• 3 ≤ N ≤ 2.500
• -100 ≤ x_i, y_i ≤ 100.
• Tidak ada 2 titik dengan koordinat yang sama.

Contoh Masukan dan Keluaran:

6
2 -2
2 2
0 -2
6 2
4 -2
4 2

6

10
1 -1
1 1
2 -1
3 1
-1 -1
0 1
0 -2
0 -3
3 -1
2 -3

10

PERHATIAN: Karena gradien dapat bernilai real (memiliki angka belakang koma), maka suatu gradien dianggap sama dengan gradien lainnya apabila perbedaan gradien tersebut lebih kecil atau sama dengan 10^-9.