Problem H

Counting Rectangles

Input: Standard Input

Output: Standard Output

Time Limit: 3 Seconds

Given n points on the XY plane, count how many regular rectangles are formed. A rectangle is regular if and only if its sides are all parallel to the axis.

Input

The first line contains the number of tests t(1<=t<=10). Each case contains a single line with a positive integer n(1<=n<=5000), the number of points. There are n lines follow, each line contains 2 integers x, y (0<=x, y<=10⁹) indicating the coordinates of a point.

Output

For each test case, print the case number and a single integer, the number of regular rectangles found.

Sample Input                             Output for Sample Input

Problemsetter: Rujia Liu, Member of Elite Problemsetters' Panel

Special Thanks: IOI2003 China National Training Team

窮舉長方形的上下兩邊，計算這兩條平行x的共同y的點個數n個。

result += C(n, 2)

// 0.120 s Rank18

#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t, cases = 0;
    int n, x, y;
    int i, j, k;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        map<int, vector<int> >g;
        for(i = 0; i < n; i++) {
            scanf("%d %d", &y, &x);
            g[x].push_back(y);
        }
        for(map<int, vector<int> >::iterator it = g.begin();
            it != g.end(); it++)
            sort(it->second.begin(), it->second.end());
        long long ans = 0, tmp;
        for(map<int, vector<int> >::iterator it = g.begin();
            it != g.end(); it++) {
            map<int, vector<int> >::iterator jt = it;
            for(jt++; jt != g.end(); jt++) {
                vector<int>::iterator pt, qt;
                pt = it->second.begin();
                qt = jt->second.begin();
                tmp = 0;
                while(pt != it->second.end() && qt != jt->second.end()) {
                    if(*pt == *qt) {
                        tmp++;
                        pt++;
                        qt++;
                    }
                    else if(*pt < *qt)
                        pt++;
                    else
                        qt++;
                }
                ans += tmp*(tmp-1)/2;
            }
        }
        printf("Case %d: %lld\n", ++cases, ans);
    }
    return 0;
}