【bzoj2338】数矩形

  • 本文为博主原创,未经许可不得转载

找矩形的方法是找对角线:两条长度相等且中点相同的线段

所以我们的做法就很显然了

处理出所有的线段,按照长度排序

然后求出所有矩形,更新面积即可

注意:不要用double,尽量避免精度误差

还有一定要用long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1510
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
typedef long long ll;
struct Point{
ll x,y;
Point(ll a=0,ll b=0):x(a),y(b){}
inline void read(){scanf("%lld%lld",&x,&y);}
inline void print(){printf("%d %d\n",x,y);}
inline Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
inline Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
inline Point operator*(const ll p){return Point(x*p,y*p);}
inline Point operator/(const ll p){return Point(x/p,y/p);}
inline bool operator==(const Point &b)const{return x==b.x&&y==b.y;}
inline bool operator< (const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}A[MAXN];
inline ll Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
inline ll Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline ll Lenth(Point A){return Dot(A,A);}//避免精度误差,不开根号
struct Line{
Point A,B,mid;
ll len;
Line(){}
Line(Point A,Point B):A(A),B(B){mid=Point(A.x+B.x,A.y+B.y); len=Lenth(A-B);}//避免精度误差,不除以2
inline bool operator==(const Line &b)const{return mid==b.mid&&len==b.len;}
inline bool operator< (const Line &b)const{return len<b.len||(len==b.len&&mid<b.mid);}
}L[MAXN*MAXN];
ll n,cnt,ans;
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE"1.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;++i) A[i].read();
for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)L[++cnt]=Line(A[i],A[j]);
sort(L+1,L+cnt+1);
for(int i=1;i<=cnt;++i)for(int j=i-1;j&&L[i]==L[j];--j)
cmax(ans,abs(Cross(L[i].A-L[j].A,L[i].B-L[j].A)));
printf("%lld\n",ans);
return 0;
}
文章目录
,