Final Indonesia National Contest 2007 :: Problem G - Sultan's Land

ACM/ICPC Indonesia National Contest 2007

Problem G

Sultan's Land

Time Limit: 1s

Sultan Al-Bandar, the ruler of Old West Sumatra Sultanate, has decided to give his land to his only son. Although the Sultan believes that his son will not misuse the land for some bad purposes, he still has some doubts on his son's capability to rule the land. Therefore, he decided to give his son a test, a puzzle test.

The Sultan drew N x N grids (virtually of course) on his land where any two adjacent grid intersections would have the same length. Then he placed some pillars on the land where each pillar was placed at one intersection. Then he summoned his son to come to the land.

"Well, my dear son, if you are to choose four pillars to form an area where each pillar serves as a corner of that area, how many possible selections are there?" asked the Sultan. His son replied him with a big smile. Just at the time the Sultan remembered that his son works for the Sultanate's Advance Combinatorial Ministry, so this problem might be too easy. Then he quickly added, "Oh! Each side of the area should be parallel to the grid I have drawn before."

To tell the truth, the Sultan himself actually had not prepared any answers since he spontaneously asked his after the big smile. Help this Sultan by writing a program to count how many possible selections can be made by applying the rules above.

Input

The input contains several test cases. Each case begins with two integers, N (2 <= N <= 100) the grid-size, and P (2 <= P <= N²) the number of pillars. Each grid will be numbered from 1 to N. The next P following lines each will contains two integers: r and c (1 <= r, c <= N) the row and column where the pillar is placed.

Input is terminated by a line containing two zeroes. This input should not be processed.

Output

For each case, output a line containing the number of possible selections can be made to form an area whose sides are parallel to the grid.

Sample Input

7 10
1 3
1 6
2 2
2 5
4 2
4 5
5 1
5 6
6 3
6 6
3 6
2 1
2 2
2 3
3 1
3 2
3 3
0 0

Sample Output

2
3

---

Problem Setter: Suhendry Effendy

---

Pembahasan 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);
    }
}

Kembali ke halaman utama