Problem G - Sultan's Land

Diberikan banyak pilar-pilar berupa titik (1<=x<=100, 1<=x<=100) dalam suatu kartesian sistem. Suatu persegi bisa dibentuk oleh 4 pillar yang terletak di 4 sudut persegi tersebut. Berapa banyak persegi yang mungkin dibentuk?

Cara yang paling gampang adalah bruteforce 4 titik: untuk setiap 4 titik, dicek apakah membentuk persegi? kalau iya, maka tambahkan ke hasil. Tapi sayangnya jumlah titik bisa mencapai 100 x 100 dimana nCk(10000, 4) = 416416712497500 itu sangat besar. Sudah pasti kena time limit exceeded.

Cara kedua adalah juga bruteforce, tetapi sedikit lebih pintar: untuk setiap kombinasi 2 baris, carilah berapa banyak persegi yang bisa dibentuk? Banyaknya kombinasi baris yang mungkin adalah nCk(100,2) = 4950 kemungkinan. Untuk setiap kombinasi 2 baris, anda dapat menghitung kemungkinan persegi yang bisa dibuat dengan cara menghitung banyak nCk(titik yang bersekutu di kolom, 2). Dengan demikian, complexity dari bruteforce ini adalah O(N^3). Untuk implementasinya silahkan lihat kode rect.c dibawah.

Anda bisa mempercepat perhitungan jumlah titik yang bersekutu di kolom untuk baris i dan baris j dengan menggunakan 2 long long variable dan menghitung jumlah persekutuan kolomnya dengan melakukan bitwise operation AND untuk baris i dan j. Lalu untuk menghitung berapa bit yang ON bisa dilakukan dengan O(1) meskipun kodenya sangatlah criptic, anda bisa lihat di bithack article ini. Sehingga complexity dari bruteforce turun menjadi O(N^2). Bagaimanapun, algo brutforce O(N^3) diatas sudah cukup cepat untuk problem ini.

#include <stdio.h>
#include <string.h>

int N,P,pillar[100][100];

int main(){
    int i,j,k,r,c,res;
    while (scanf("%d %d",&N,&P)!=EOF && (N||P)){
        memset(pillar,0,sizeof(pillar));
        for (i=0; i<P; i++){
            scanf("%d %d",&r,&c);
            pillar[r-1][c-1] = 1;
        }

        res = 0;
        for (i=0; i<N; i++)
            for (j=i+1; j<N; j++){
                int c = 0;
                for (k=0; k<N; k++)
                    if (pillar[i][k] && pillar[j][k])
                        c++;

                res += c*(c-1)/2; // nCk(c,2) = c diambil 2 = c*(c-1)/2
            }
        printf("%d\n",res);
    }
}

Lihat problem lain:

1. Minimum Swap
2. GCD!
3. Playing With Domino
4. Email from the Professor
5. Panda Number
6. Jakarta Traffic Jam
7. Sultan's Land
8. Tree Median