Tiang Pemancar

Tiang Pemancar

Cerita Pengantar

Pak Dengklek kini bekerja sampingan di suatu stasiun televisi ternama. Suatu hari, Pak Dengklek mendapatkan tugas untuk memasang tiga tiang pemancar perdana di suatu daerah yang baru berkembang. Untuk membantu menyelesaikan tugas tersebut, Pak Dengklek telah mendapatkan informasi koordinat titik-titik di mana tiang pemancar boleh didirikan.

Berdasarkan pengalaman Pak Dengklek, diketahui juga bahwa tiga tiang pemancar tersebut sebaiknya dibangun sedemikian rupa sehingga membentuk pola segitiga siku-siku yang salah satu sisinya sejajar dengan sumbu vertikal (sumbu y) dan salah satu sisi lainnya sejajar dengan sumbu horisontal (sumbu x).

Untuk setiap cara penempatan pemancar yang mungkin dilakukan, Pak Dengklek perlu memperhitungkan beberapa hal lain seperti dampaknya terhadap anggaran dana, kualitas siaran, dan lain-lain. Tentunya setiap perhitungan membutuhkan waktu. Semakin banyak kemungkinan cara, semakin banyak pula waktu yang Pak Dengklek perlukan.

Tugas Anda

Anda akan diberikan informasi koordinat N buah titik di mana tiang pemancar boleh dibangun. Bantulah Pak Dengklek untuk menentukan berapa banyak kemungkinan segitiga siku-siku yang dapat dibentuk dari titik-titik tersebut. Dua buah cara dianggap berbeda jika terdapat setidaknya satu tiang yang lokasinya berbeda di antara kedua cara tersebut.

Format Masukan

Baris pertama berisi sebuah bilangan bulat N yang menyatakan banyaknya titik. N baris berikutnya masing-masing berisi dua buah bilangan bulat Xi dan Yi dipisahkan oleh sebuah spasi yang menyatakan posisi horisontal dan vertikal dari suatu titik.

Format Keluaran

Sebuah baris berisi sebuah bilangan bulat yang menyatakan banyaknya cara penempatan pemancar yang perlu Pak Dengklek perhitungkan.

Contoh Masukan 1

3
2 2
0 0
1 1

Contoh Keluaran 1

0

Contoh Masukan 2

4
0 0
1 0
1 1
0 1

Contoh Keluaran 2

4

Contoh Masukan 3

5
0 0
2 0
2 2
0 2
1 1

Contoh Keluaran 3

4

Penjelasan Contoh

Pada contoh pertama, ketiga titik berada pada sebuah garis lurus, sehingga tidak mungkin pola segitiga siku-siku terbentuk. Pada contoh kedua, empat titik membentuk persegi sempurna, oleh karena itu terdapat empat cara membentuk segitiga siku-siku.

Batasan dan Penilaian

Terdapat 3 subsoal pada soal ini. Untuk setiap kasus uji pada semua subsoal, batasan runtime adalah 1 detik dan batasan memori adalah 16 MB.

  • Batasan khusus untuk subsoal 1 (bernilai 40 poin): 1 ≤ N ≤ 50.
  • Batasan khusus untuk subsoal 2 (bernilai 30 poin): 1 ≤ N ≤ 5000.
  • Batasan khusus untuk subsoal 3 (bernilai 30 poin): 1 ≤ N ≤ 500000.
  • Batasan lainnya untuk semua subsoal: 0 ≤ Xi ≤ 5000, 0 ≤ Yi ≤ 5000, dan tidak ada dua titik yang memiliki posisi yang sama.

Setiap subsoal dapat memiliki lebih dari satu kasus uji. Untuk mendapatkan poin dari suatu subsoal, program Anda harus berhasil menjawab dengan benar semua kasus uji pada subsoal tersebut tanpa melanggar batasan runtime, batasan memori, atau aturan dasar lainnya.