BZOJ 1356 [Baltic2009]Rectangle 数学

题意: 平面上n个点，求选出四个点构成矩形的最大面积。 解析: 四个点构成矩形有个性质， 就是四点共圆，并且两条对角线都是直径。 所以我们可以考虑首先预处理出来任意两点所确定的圆。 然后我们只需要在同一个圆中暴力枚举成对的点对即可。 处理圆的话，，避免小数我们可以考虑使横纵坐标乘2，直径平方即可。 为什么这个复杂度敢写呢？ 我们只需要考虑一个圆上能有多少对整点呢？ 我虽然不会计算但是应该不会有很多。 所以我们的复杂度是O(n*n>>1*(k*k>>1)) k为圆上的整点对。 不虚。。 代码:

;ll;int n;double ans;struct Point{int x,y;Point(){}Point(int _x,int _y):x(_x),y(_y){}friend istream& operator >> (istream &_,Point &a){scanf(“%d%d”,&a.x,&a.y);return _;}Point operator + (const Point &a){return Point(x+a.x,y+a.y);}Point operator – (const Point &a){return Point(x-a.x,y-a.y);}double operator * (const Point &a){return (double)x*a.x+(double)y*a.y;}}pt[N];struct Cir{int x,y,len;int no1,no2;}cir[(N*N)>>1];bool cmp(Cir a,Cir b){if(a.x==b.x){if(a.y==b.y){return a.len<b.len;}else return a.y<b.y;}else return a.x<b.x;}bool operator == (Cir a,Cir b){if(a.x==b.x&&a.y==b.y&&a.len==b.len)return 1;return 0;}double get_dis(Point a,Point b){return sqrt((a-b)*(a-b));}void calc(int l,int r){if(l==r)return ;for(int i=l;i<=r;i++){for(int j=l;j<i;j++){double l1=get_dis(pt[cir[i].no1],pt[cir[j].no1]);double l2=get_dis(pt[cir[j].no1],pt[cir[i].no2]);ans=max(ans,l1*l2);}}}int tot;int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++)cin>>pt[i];for(int i=1;i<=n;i++){for(int j=1;j<i;j++){int x=pt[i].x+pt[j].x;int y=pt[i].y+pt[j].y;int len=(pt[i].x-pt[j].x)*(pt[i].x-pt[j].x)+(pt[i].y-pt[j].y)*(pt[i].y-pt[j].y);cir[++tot].x=x,cir[tot].y=y,cir[tot].len=len,cir[tot].no1=i,cir[tot].no2=j;}}sort(cir+1,cir+tot+1,cmp);int j;for(int i=1;i<=tot;i=j+1){j=i;while(cir[i]==cir[j+1])j++;calc(i,j);}printf(“%.0lf\n”,ans);}

其实，每个人都是幸福的。只是，你的幸福，常常在别人眼里。