BZOJ2338:[HNOI2011]数矩形 暴力+计算几何

思路:

首先搞出所有的线段,然后中点相同的放在一起,并且长度相同的放在一起.

那么,中点相同并且长度相同,这两个线段就能够构成一个矩形.

这样的线段不会超过\(O(n)\)条,所以我们可以直接暴力枚举.

(其实我觉得可以把所有的线段以中点为原点进行极角序排序,然后我们就是要找出两条线段使得它们之间的夹角尽可能接近90,这大概就可以线性扫描了.)

本代码完全避免了精度问题!速来点赞!

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y):x(_x),y(_y){}
 
    bool operator<(const Point&B)const{return(x!=B.x)?x<B.x:y<B.y;}
    bool operator!=(const Point&B)const{return(x!=B.x)||(y!=B.y);}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
};
LL Cross(const Point&a,const Point&b){return(LL)a.x*b.y-(LL)a.y*b.x;}
LL Getans(Point p1,Point p2,Point q1,Point q2){
    LL res=Cross(p1-q1,p1-q2);
    return res<0?-res:res;
}
 
int gcd(int a,int b){return(!b)?a:gcd(b,a%b);}
 
struct Double{
    int x,y;
    Double(){}
    Double(int _x,int _y):x(_x),y(_y){}
 
    bool operator<(const Double&B)const{return(LL)x*B.y<(LL)y*B.x;}
};
 
 
#define N 1510
struct Segment{
    Point P1,P2;LL dis;
    bool insequal(const Segment&B)const{
        if(P1.x+P2.x!=B.P1.x+B.P2.x)return 0;
        if(P1.y+P2.y!=B.P1.y+B.P2.y)return 0;
        return 1;
    }
    bool operator<(const Segment&B)const{
        if(P1.x+P2.x!=B.P1.x+B.P2.x)return P1.x+P2.x<B.P1.x+B.P2.x;
        if(P1.y+P2.y!=B.P1.y+B.P2.y)return P1.y+P2.y<B.P1.y+B.P2.y;
        return dis<B.dis;
    }
    bool operator==(const Segment&B)const{return insequal(B)&&dis==B.dis;}
}S[N*N>>1];int id;
 
int x[N],y[N],n;
 
inline LL sqr(int x){
    return(LL)x*x;
}
 
int main(){
    scanf("%d",&n);register int i,j,k,p;for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
 
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)++id,S[id].P1=Point(x[i],y[i]),S[id].P2=Point(x[j],y[j]),S[id].dis=sqr(x[i]-x[j])+sqr(y[i]-y[j]);
     
    sort(S+1,S+id+1);
 
    LL res=0;
    for(i=1;i<=id;i=j+1){
        for(j=i;j!=id&&S[j]==S[j+1];++j);
        for(k=i;k<=j;++k)for(p=k+1;p<=j;++p)res=max(res,Getans(S[k].P1,S[k].P2,S[p].P1,S[p].P2));
    }
 
    cout<<res<<endl;
 
    return 0;
}