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#include #include #include 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;}