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 (≤ x, y ≤ 109
) 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
2
5
0 0
2 0
0 2
2 2
1 1
3
0 0
0 30
0 900
Sample Output
Case 1: 1
Case 2: 0
题意：给你n个点 ，问你这些点能够组成多少个 长宽和坐标轴平行的 矩形
题解：按照x排序，在y轴平行下，选择不同直线组合，满足两y轴上的点相等就是一种， 对于一堆相等的 我们用组合数就好了
//meek
///#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
#define fi first
#define se second
#define MP make_pair const int N=;
const ll INF = 1ll<<;
const int inf = <<;
const int mod= ;
const int M = ; struct ss{
int x,y;
}a[N],p[N*N];
int cnt;
int cmp(ss s1,ss s2) {
if(s1.x == s2.x) return s1.y<s2.y;
return s1.x<s2.x;
}
void init() {
cnt = ;mem(p);
}
ll solve() {
ll ans = ;
for(int i = ;i < cnt; ) {
int now = i+;
while(p[i].x == p[now].x && p[i].y == p[now].y) now++;
ll c = now - i;
if(c>=) ans += c*(c-)/;
i = now;
}
return ans;
}
int main() {
int T,n,x,y,cas = ;
scanf("%d",&T);
while(T--) {
init();
scanf("%d",&n);
for(int i=;i<=n;i++) {
scanf("%d%d",&x,&y);
a[i].x = x;
a[i].y = y;
}
sort(a+,a+n+,cmp);
cnt = ;
for(int i=;i<=n;i++) {
for(int j=i+;j<=n;j++) {
if(a[i].x != a[j].x) {
break;
}
p[cnt].x = a[i].y;
p[cnt].y = a[j].y;
cnt++;
}
}
printf("Case %d: ",cas++);
sort(p,p+cnt,cmp);
printf("%lld\n",solve());
}
return ;
}
代码