矩形数量-C++-穷举解法

Question

矩形数量
给出平面上一些点(少于50个），坐标都是整数(|xi|,|yi| <= 109)，有可能重复。问存在多少个以这些点为顶点的平行于坐标轴的不同矩形。(两个矩形如果四个顶点坐标都相同，就算相同的矩形)
输入
第一行一个整数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<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 1002
#define memset0(a) memset(a,0,sizeof(a))
#define EPS 1e-8

struct Pt//point 点的结构
{
    int x, y;
    Pt() {}
    Pt(int x, int y) :x(x), y(y) {}
    bool operator<(const Pt &b)const
    {
        return y != b.y ? y < b.y : x < b.x;//y坐标升序优先 x坐标升序其次
    }
} pts[MAXN];
int N;//点总数
int fun()
{
    for (int p = 0; p < N; p++)
        scanf("%d%d", &pts[p].x, &pts[p].y);//input
    sort(pts, pts + N);//排序 方便二分
    int ans = 0;
    for (int p = 0; p < N; p++)//枚举第一个点
        for (int i = p + 1; i < N; i++)  //枚举另一个点画对角线
        {
            Pt p2(pts[p].x + pts[i].x - pts[p].y + pts[i].y, pts[p].x - pts[i].x + pts[p].y + pts[i].y);//point_2 额认为前面枚举的一个是点1 一个是点3 计算所得的点2的坐标是实际的二倍 因为还得判断有无小数
            if (!(p2.x & 1) && !(p2.y & 1))  //如果点2的横坐标或纵坐标带小数 由于输入都是整数 显然不会存在
            {
                p2.x /= 2, p2.y /= 2;//这时点2坐标才正确
                Pt p4((pts[p].y - pts[i].y + pts[p].x + pts[i].x) / 2, (pts[p].y + pts[i].y - pts[p].x + pts[i].x) / 2);//算出点4坐标
                ans += binary_search(pts, pts + N, p2) && binary_search(pts, pts + N, p4);
            }
        }
    return ans / 2;//同一个正方形的两条对角线都会被枚举一次 因而除以2
}
int main(void)
{
    int i,m;
    scanf("%d", &m);
    for(i=0; i<m; i++)
    {
        scanf("%d", &N);
        if(i!=m-1)
            printf("%d\n", fun());//output
        else
            printf("%d", fun());
    }

}