关于#平面#的问题，如何解决？

Question

题目描述
给出平面上一些点(少于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

Answer 1

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