hdu 2428

题目意思是给N(小于1000)个点，问这些点能构成多少个边与坐标轴平行的正方形。我的做法是先把所有点排序，枚举两个点作为正方形的一边，进而算出另外的两个顶点，然后十分查找这两个点是否都存在，最坏情况下复杂度为n^2 logn。

/*
 * hdu2428/win.c
 * Created on: 2011-8-23
 * Author    : ben
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAXN 1005

typedef struct {
    int x;
    int y;
} MyPoint;

MyPoint points[MAXN];
int N, ans;

int cmp(const void *a, const void *b) {
    MyPoint *p1, *p2;
    p1 = (MyPoint *) a;
    p2 = (MyPoint *) b;
    if (p1->x != p2->x) {
        return p1->x - p2->x;
    } else {
        return p1->y - p2->y;
    }
}

int exist(int x, int y) {
    int mid, high, low, temp;
    MyPoint p;
    p.x = x;
    p.y = y;
    low = 0;
    high = N - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        temp = cmp(&p, &points[mid]);
        if (temp == 0) {
            return (points[mid].x == x && points[mid].y == y);
        } else if (temp > 0) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    if (low < 0 || low >= N) {
        return 0;
    }
    return (points[low].x == x && points[low].y == y);
}

void work() {
    int T, i, j, temp;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        for (i = 0; i < N; i++) {
            scanf("%d%d", &points[i].x, &points[i].y);
        }
        qsort(points, N, sizeof(MyPoint), cmp);
        ans = 0;
        for (i = 0; i < N; i++) {
            for (j = i + 1; j < N; j++) {
                if (points[i].x != points[j].x) {
                    break;
                }
                temp = points[j].y - points[i].y;
                if (exist(points[i].x + temp, points[i].y)
                        && exist(points[j].x + temp, points[j].y)) {
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    work();
    return 0;
}