Tags

1. Tiang Pemancar

Pembuat soal: Brian Marshal

URL:

Ini adalah soal dengan banyak solusi dengan nilai penuh terbanyak di OSN ini.

Asumsikan banyaknya titik dengan posisi horizontal x ada sebanyak A[x], dan banyaknya titik dengan posisi horizontal y ada sebanyak B[y]. Lakukan prekomputasi untuk menghitung isi dari A dan B.

Untuk masing-masing titik dengan koordinat (x, y), banyaknya segitiga siku-siku dengan titik sudut siku-siku berada pada (x, y) dan ketiga titik sudutnya berasal dari titik-titik inputan ada sebanyak:

(A[x] – 1) (B[y] – 1).

Mengapa? Karena kedua titik sudut segitiga siku-siku tersebut salah satunya pasti memiliki posisi horizontal yang sama dengan (x,y), dan satu lagi pasti memiliki posisi vertikal yang sama dengan (x,y). Banyaknya titik dengan posisi horizontal yang sama dengan (x, y) adalah A[x], dan banyaknya titik dengan posisi horizontal yang sama dengan (x, y) selain (x, y) adalah (A[x] – 1). Hal yang serupa berlaku pada titik sudut yang lain, sehingga banyak titik dengan posisi vertikal yang sama dengan (x, y) selain (x, y) adalah (B[y] – 1). Oleh karena itu, banyaknya segitiga siku-siku yang kita inginkan hanyalah perkalian kedua angka tersebut, yakni (A[x] – 1) (B[y] – 1).

Solusi untuk permasalahan ini adalah penjumlahan dari semua (A[x] – 1) * (B[y] – 1) yang mana (x, y) adalah bagian dari titik-titik masukan.

Advertisements