Description
Problem H
Counting Rectangles
Input: Standard Input
Output:Standard Output
Time Limit: 3Seconds
Given n points on the XY plane, count how many regular rectanglesare formed. A rectangle is regular if and only if its sides are all parallel tothe axis.
Input
Thefirst 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 2integers
x, y (0<=x, y<=109)indicating the coordinates of a point.
Output
Foreach test case, print the case number and a single integer, the number ofregular rectangles found.
SampleInput Output for Sample Input
|
2 5 0 0 2 0 0 2 2 2 1 1 3 0 0 0 30 0 900 |
Case 1: 1 Case 2: 0 |
题意：给定平面上的n个点，统计它们能组成多少个边平行于坐标轴的矩形
思路：题目要求平行于坐标轴，那么我们先找同一x轴的两个点组成的线段，保存两个点的y轴坐标，那么我们仅仅要再找两个端点在y轴平行的这样就能找到矩形了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 5010; struct Point {
int x, y;
bool operator< (const Point &a) const {
if (x != a.x)
return x < a.x;
return y < a.y;
}
} p[maxn]; struct Edge {
int y1, y2;
Edge() {}
Edge(int y1, int y2) {
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[maxn*maxn];
int n; int main() {
int t;
int cas = 1;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
sort(p, p+n);
int num = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++) {
if (p[i].x != p[j].x)
break;
e[num++] = Edge(p[i].y, p[j].y);
}
sort(e, e+num);
int tmp = 1, ans = 0;
for (int i = 1; i < num; i++) {
if (e[i].y1 == e[i-1].y1 && e[i].y2 == e[i-1].y2)
tmp++;
else {
ans += tmp * (tmp-1) / 2;
tmp = 1;
}
}
ans += tmp * (tmp-1) / 2;
printf("Case %d: %d\n", cas++, ans);
}
return 0;
}