10574 - Counting Rectangles

题目链接

题意：给定一些点，求可以成几个边平行于坐标轴的矩形

思路：先把点按x排序，再按y排序。然后用O(n^2)的方法找出每条垂直x轴的边，保存这些边两点的y坐标y1, y2。之后把这些边按y1排序，再按y2排序。用O(n)的方法找出有几个连续的y1, y2都相等。那么这些边两两是能构成矩形的。为C2cnt种。然后累加起来就是答案

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

const int N = 5005;

int t, n;

struct Point {

    int x, y;

    void read() {

    scanf("%d%d", &x, &y);

    }

    bool operator < (const Point a) const {

    if (x != a.x)

        return x < a.x;

    return y < a.y;

    }

} p[N];

struct Edge {

    int y1, y2;

    Edge(int y1 = 0, int y2 = 0) {

    this->y1 = y1;

    this->y2 = y2;

    }

    bool operator < (const Edge a) const {

    if (y1 != a.y1)

        return y1 < a.y1;

    return y2 < a.y2;

    }

} e[N * N / 2];

int main() {

    int cas = 0;

    scanf("%d", &t);

    while (t--) {

    scanf("%d", &n);

    for (int i = 0; i < n; i++)

        p[i].read();

    sort(p, p + n);

    int en = 0;

    for (int i = 0; i < n; i++) {

        for (int j = i + 1; j < n; j++) {

        if (p[j].x != p[i].x) break;

        e[en++] = Edge(p[i].y, p[j].y);

        }

    }

    sort(e, e + en);

    long long cnt = 1, ans = 0;

    for (int i = 1; i < en; i++) {

        if (e[i].y1 == e[i - 1].y1 && e[i].y2 == e[i - 1].y2)

        cnt++;

        else {

        ans += cnt * (cnt - 1) / 2;

        cnt = 1;

        }

    }

    ans += cnt * (cnt - 1) / 2;

    printf("Case %d: %lld\n", ++cas, ans);

    }

    return 0;

}