P3217 [HNOI2011] 数矩形

· · 题解

由于其他 dalao 的题解本蒟蒻看不懂，所以写了这篇比较好理解的题解。

前置知识

  1. 只有当两条线段的中点重合，线段长度相同，才会构成矩形。
  2. 勾股定理求线段 AB 的长度：\sqrt{\left|X_A-X_B\right|^2+\left|Y_A-Y_B\right|^2}。
  3. 此代码要开吸氧优化，时间能下降到原时间的 \frac{1}{3}，还是比较可观的。

步骤

一、储存每条线段的信息

  1. 在这 n 个点中，一共有 \frac{n(n-1)}{2} 条线段，以它们的长度为分类的标准，储存该线段的两个节点的 x,y 坐标和中点的坐标。
  2. 线段长度的计算：线段长度可用勾股定理求，但求出的可能是无理数，所以不开根号存储更好。

二、计算矩形面积

  1. 对于线段长度相同的线段，以中点坐标为根据排序，找到中点坐标相同的几条线段，计算其中任意两条线段组成的矩形的面积。
  2. 既然找到了两条线段共四个点，也可用勾股定理求出矩形的长和宽，这样可求出此矩形的面积。

三、输出

选出矩形面积中最大的即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1.5e3+10;
const int M=1e6+10;
int n,x[N],y[N],cnt=0,ans=0;
struct node{//存储线段两个端点和中点的坐标 
    int x1,y1,x2,y2;
    long double mid_x,mid_y;
};
map<int,int>mp;
vector<node>g[M];
int rec(int p){//辅助勾股定理的计算 
    return abs(p)*abs(p);
}
bool cmp(node p,node q){//按中点排序 
    if(p.mid_x==q.mid_x)return p.mid_y<q.mid_y;
    return p.mid_x<q.mid_x;
}
signed main(){
    cin >>n;//输入 
    for(int i=1;i<=n;i++){
        cin >>x[i]>>y[i];
    }
    for(int i=1;i<=n-1;i++){//存储线段 
        for(int j=i+1;j<=n;j++){
            int len=rec(x[i]-x[j])+rec(y[i]-y[j]);//勾股定理 
            if(!mp[len])mp[len]=++cnt;
            g[mp[len]].push_back({x[i],y[i],x[j],y[j],(x[i]+x[j])/2.0,(y[i]+y[j])/2.0});
        }
    }
    for(int i=1;i<=cnt;i++){//计算矩形面积 
        sort(g[i].begin(),g[i].end(),cmp);
        for(int j=0;j<g[i].size();j++){
            //判断两条线段的中点是否相同
            int id=j;
            while(g[i][id].mid_x==g[i][j].mid_x&&g[i][id].mid_y==g[i][j].mid_y&&id<g[i].size()){
                id++;
            }
            for(int k=j;k<id-1;k++){//计算矩形面积 
                for(int l=k+1;l<=id-1;l++){
                    node p=g[i][k],q=g[i][l];
                    int a=rec(p.x1-q.x1)+rec(p.y1-q.y1);
                    int b=rec(p.x1-q.x2)+rec(p.y1-q.y2);
                    ans=max(ans,(int)(sqrt(a)*sqrt(b)));//求最大值 
                    //这里直接求长的平方乘宽的平方会炸 
                }
            }
        }
    }
    cout <<ans;//输出 
    return 0;
}