【计算几何】bzoj2338 [HNOI2011]数矩形

对于两条线段，若其中点重合，且长度相等，那么它们一定是某个矩形的对角线。

N*N地处理出所有线段，排序，对每一部分中点重合、长度相等的线段进行暴力枚举，更新答案。

用 long double 注意EPS的设置，卡精度。

注意数组大小的设置，容易MLE。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<iostream>
 5 using namespace std;
 6 #define EPS 0.000000000000001
 7 #define N 1501
 8 typedef long long ll;
 9 typedef long double llf;
10 llf sqr(const llf &x){return x*x;}
11 struct Point
12 {
13     llf x,y;
14     Point(const llf &a,const llf &b){x=a;y=b;}
15     Point(){}
16     void Read(){cin>>x>>y;}
17 };
18 typedef Point Vector;
19 struct Line
20 {
21     Point l,r,m; llf len;
22     Line(const Point &a,const Point &b){l=a;r=b;}
23     Line(){}
24     void Init(){m=Point((l.x+r.x)/2.0,(l.y+r.y)/2.0);len=sqrt(sqr(l.x-r.x)+sqr(l.y-r.y));}
25 };
26 bool Equal(const llf &a,const llf &b){return fabs(a-b)<EPS ? 1 : 0;}
27 bool Less(const llf &a,const llf &b){return a-b<(-EPS) ? 1 : 0;}
28 bool LeEqu(const llf &a,const llf &b){return a-b<EPS ? 1 : 0;}
29 bool operator < (const Point &a,const Point &b)
30 {return (!Equal(a.x,b.x))?Less(a.x,b.x):Less(a.y,b.y);}
31 bool operator == (const Point &a,const Point &b)
32 {return (Equal(a.x,b.x)&&Equal(a.y,b.y)) ? 1 : 0;}
33 bool operator != (const Point &a,const Point &b){return a==b ? 0 : 1;}
34 bool operator < (const Line &a,const Line &b)
35 {return a.m!=b.m ? a.m<b.m : Less(a.len,b.len);}
36 bool operator == (const Line &a,const Line &b)
37 {return (Equal(a.len,b.len)&&a.m==b.m) ? 1 : 0;}
38 bool operator != (const Line &a,const Line &b){return a==b ? 0 : 1;}
39 Vector operator - (const Point &a,const Point &b){return Vector(a.x-b.x,a.y-b.y);}
40 llf Cross(const Vector &a,const Vector &b){return a.x*b.y-a.y*b.x;}
41 int n,m,head;
42 Point p[N];
43 llf ans;
44 Line lines[N*N>>1];
45 int main()
46 {
47     scanf("%d",&n);
48     for(int i=1;i<=n;i++) p[i].Read();
49     for(int i=1;i<=n;i++)
50       for(int j=i+1;j<=n;j++)
51         if(p[i]!=p[j])
52           {
53             lines[++m]=Line(p[i],p[j]);
54             lines[m].Init();
55           }
56     sort(lines+1,lines+m+1);
57     for(int i=1;i<=m;i++)
58       {
59         if(lines[i]!=lines[i-1]) head=i;
60         if(lines[i]!=lines[i+1])
61           if(i-head)
62             {
63               for(int j=head;j<=i;j++)
64                 for(int k=j+1;k<=i;k++)
65                   ans=max(ans,fabs(Cross(lines[j].l-lines[j].m,lines[k].l-lines[k].m))
66                   +fabs(Cross(lines[j].l-lines[j].m,lines[k].r-lines[k].m)));
67             }
68       }
69     printf("%lld
",(ll)ans);
70     return 0;
71 }