题解 P3217 【[HNOI2011]数矩形】

· · 题解

严格 O(n^2\log n) 的做法。

现行的大多数题解都是枚举两条对角线进行处理的——这就导致必须 O(n^{2.5}) 地枚举完全部的合法矩形进行判断。但如果我们转换思路，不枚举对角线，而枚举矩形的一对平行的边呢？

考虑两条线段如何才是一对合法的矩形边。它们必须满足如下三点：

  1. 斜率相等。这个可以通过叉积简单计算（线段所代表的向量叉积为 0 则斜率相等）。

  2. 长度相等。这个也可以简单计算。

  3. 构成直角。这个可以通过计算夹角加以比较（直角则有点积为 0）。

任意两条满足上述三个条件的线段，均可构成一个合法的矩形。然而，对于一组斜率相等、长度相等、两两构成直角的线段，只有最边缘的两条所形成的矩形具有最大的面积。

于是我们内部再按照夹角是否 \leq180^\circ 加以排序，具体可以通过叉积大小加以比较。

然后就排序后使用双针找到一段合法段中最左方和最右方的两条线段，并更新答案即可。

瓶颈在于排序。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll res;
struct Vector{
    int x,y;
    Vector(){}
    Vector(int X,int Y){x=X,y=Y;}
    friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
    friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
    friend ll operator &(const Vector &u,const Vector &v){return 1ll*u.x*v.y-1ll*u.y*v.x;}//cross times
    friend ll operator |(const Vector &u,const Vector &v){return 1ll*u.x*v.x+1ll*u.y*v.y;}//point times
    ll operator ~()const{return 1ll*x*x+1ll*y*y;}//the modulo of a vector
    void read(){scanf("%d%d",&x,&y);}
    void print(){printf("(%d,%d)",x,y);}
}p[1510];
typedef Vector Point;
struct Line{
    Point x,y;
    Vector z;
    Line(){}
    Line(Point X,Point Y){x=X,y=Y,z=Y-X;}
    friend bool operator <(const Line &u,const Line &v){
        if(u.z&v.z)return (u.z&v.z)<0;
        if(~u.z!=~v.z)return ~u.z<~v.z;
        if((u.x-v.x)|v.z)return ((u.x-v.x)|v.z)<0;
        return ((u.x-v.x)&v.z)<0;
    }
    friend bool operator ==(const Line &u,const Line &v){
        if(u.z&v.z)return false;
        if(~u.z!=~v.z)return false;
        if((u.x-v.x)|v.z)return false;
        return true;
    }
}l[2250100];
typedef Line Segment;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)p[i].read();
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(p[i].y<p[j].y||(p[i].y==p[j].y&&p[i].x<p[j].x))l[++m]=Segment(p[i],p[j]);
    sort(l+1,l+m+1);
    for(int i=1,j=1;i<=m;i=j){
        while(j<=m&&l[i]==l[j])j++;
        res=max(res,abs(l[i].z&(l[i].x-l[j-1].x)));
    }
    printf("%lld\n",res);
    return 0;
}