题目描述
给出平面上一些点(少于50个），坐标都是整数(|xi|,|yi| <= 10^9)，有可能重复。
问存在多少个以这些点为顶点的平行于坐标轴的不同矩形。(两个矩形如果四个顶点坐标都相同，就算相同的矩形)
输入格式
第一行一个整数T(T <= 100)表示测试数据的组数 对于每组数据 第一行一个整数n，表示点的数量 下面n行每行两个整数xi,yi表示点的坐标
输出格式
T行，每行一个整数表示以这些点为顶点的平行于坐标轴的矩形个数
样例
样例输入
1
7
0 0
0 1
0 2
1 0
1 1
1 2
0 0
样例输出
3
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int t, n, x, y, count = 0;
cin >> t;
for (int i = 0; i < t; i++)
{
cin >> n;
vector<pair<int, int>> points;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
points.push_back({x, y});
}
// 排序
sort(points.begin(), points.end());
// 去重
auto last = unique(points.begin(), points.end());
points.erase(last, points.end());
/*
points[j] +-----------+ points[l]
| |
| |
points[i] +-----------+ points[k]
*/
for (size_t i = 0; i < points.size(); i++)
{
for (size_t j = i + 1; j < points.size(); j++)
{
if (points[i].first == points[j].first)
{
for (size_t k = j + 1; k < points.size(); k++)
{
if (points[k].first != points[i].first && points[k].second == points[i].second)
{
for (size_t l = k + 1; l < points.size(); l++)
{
if (points[l].first == points[k].first && points[l].second == points[j].second)
count++;
}
}
}
}
}
}
}
cout << count << endl;
return 0;
}
或
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 100;
PII arr[N];
int main() {
int n, sum = 0, t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i].first >> arr[i].second;
sort(arr, arr + n);
n = unique(arr, arr + n) - arr; // 必须要先排序，再去重，然后才二分查找
for (int i = 0; i < n; i++) {
int x = arr[i].first + 1, y = arr[i].second + 1;
// lower_bound是库函数二查找，找到比当前arr[i]的坐标大1的数在什么位置
int j = lower_bound(arr, arr + n, make_pair(x, y)) - arr;
sum += n - j;
}
cout << sum << endl;
}
return 0;
}
或
#include<iostream>
#include <math.h>
using namespace std;
double x[50],y[50];
double f[50]= {-65536};
int p=0;
bool isRectangle( double x1, double y1,
double x2, double y2,
double x3, double y3,
double x4, double y4)
{
double cx=(x1+x2+x3+x4)/4;
double cy=(y1+y2+y3+y4)/4;
double dd1= sqrt(cx-x1)+ sqrt(cy-y1);
double dd2= sqrt(cx-x2)+ sqrt(cy-y2);
double dd3= sqrt(cx-x3)+ sqrt(cy-y3);
double dd4= sqrt(cx-x4)+ sqrt(cy-y4);
return abs(dd1 - dd2) < 1E-6 &&
abs(dd1 - dd3) < 1E-6 &&
abs(dd1 - dd4) < 1E-6;
}
int main()
{
int count=0;
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
for(int j=0; j<n; j++)
{
cin >> x[j];
cin >> y[j];
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
for(int k=0; k<n; k++)
for(int h=0; h<n; h++)
{
if(isRectangle(x[i],y[i],
x[j],y[j],
x[k],y[k],
x[h],y[h]))
{
count++;
double tem=x[i]*y[i]*x[j]*y[j]*x[k]*y[h]*x[h]*y[h];
for(int point=0; point<p; point++)
if(tem==f[point])
{
count--;
break;
}
f[p++]=tem;
}
}
}
}
cout << count << endl;
return 0;
}
采用枚举对角线的方式，二重循环，另外要去重
单次复杂度约为O(N^2)
代码：
#include<bits/stdc++.h>
using namespace std;
int T,n;
struct Node{
int x,y;
bool operator<(const Node&a)const{
return x<a.x||x==a.x&&y<a.y;
}
bool operator==(const Node&a)const{
return x==a.x&&y==a.y;
}
}a[1009];
struct Squ{
Node a[4];
bool operator<(const Squ&A)const{
return a[1]<A.a[1];
}
bool eq(const Squ&A){
return a[1]==A.a[1]&&a[2]==A.a[2]&&a[3]==A.a[3]&&a[4]==A.a[4];
}
bool operator==(const Squ&A)const{
Squ tmp=*this;
do{
if(tmp.eq(A))return 1;
}while(next_permutation(tmp.a,tmp.a+4));
return 0;
}
};
set<Squ>sq;
set<Node>h;
set<Node>::iterator it;
void quchong() {
h.clear();
for(int i=1;i<=n;i++)h.insert(a[i]);
it=h.begin();
n=h.size();
int x=0;
for(;it!=h.end();it++)a[++x]=*it;
}
int main() {
Node f1,f2;
cin>>T;
for(int i=1;i<=T;i++) {
sq.clear();
cin>>n;
for(int j=1;j<=n;j++)cin>>a[j].x>>a[j].y;
//枚举对角线
quchong();//去重同时排序，方便后面的二分查找
for(int k=1;k<=n;k++)
for(int m=k+1;m<=n;m++) {
f1=(Node){a[m].x,a[k].y},f2=(Node){a[k].x,a[m].y};//另外两点
if(!(*lower_bound(a+1,a+1+n,f1)==f1&&*lower_bound(a+1,a+1+n,f2)==f2))continue;
if(lower_bound(a+1,a+1+n,f1)-a==k||lower_bound(a+1,a+1+n,f1)-a==m)continue;
if(lower_bound(a+1,a+1+n,f2)-a==k||lower_bound(a+1,a+1+n,f2)-a==m)continue;
Squ tmp;
tmp.a[0]=a[k];
tmp.a[1]=f1;
tmp.a[2]=a[m];
tmp.a[3]=f2;
sq.insert(tmp);
}
cout<<sq.size()<<endl;
}
return 0;
}