[bzoj1356]Rectangle[Baltic2009][几何常识乱搞]

虽然说是几何常识乱搞，但是想不到啊。。

题意：n个点取4个组成矩形，使面积最大，求面积。 n<=1500

题解：

　　1.对角线相等且相互交于中点的四边形是矩形。

　　2.矩形四点共圆。

　　所以$n^2$枚举边，把线段中点和长度打包pair

　　如果两条线的pair相等则可以构成一个圆，把相等的线段平方级枚举即可。

　　考虑一个圆上的整点不多，常数小，所以没有T。。注意精度问题。

　　【学习】http://blog.csdn.net/wzq_qwq/article/details/49005387

　　感觉自己代码自带大常数。。有看出原因的，望留言指正谢谢：）

 #include <bits/stdc++.h>

 using namespace std;

 struct node

 {

     pair<int,int>    pr; long long len; int    x,y;

     bool    operator<(const node & temp)const

     {

         if(pr!=temp.pr)return pr<temp.pr;

         return len<temp.len;

     }

     bool    operator>(const node & temp)const

     { return temp<*this; }

     bool    operator==(const node & temp)const

     { return !(*this<temp) && !(temp<*this); }

 }vec[*];

 pair<int,int>    p[];

 double Dis(const int x,const int y)

 {

     return sqrt(1.0*(p[x].first-p[y].first)*(p[x].first-p[y].first)+

         1.0*(p[x].second-p[y].second)*(p[x].second-p[y].second));

 }

 int main()

 {

     int    n,tot=;

     scanf("%d",&n);

     for(int i=;i<=n;++i)

         scanf("%d%d",&p[i].first,&p[i].second),

             p[i].first<<=,p[i].second<<=;

     for(int i=;i<=n;++i) for(int j=;j<=n;++j)

       vec[++tot]=(node)

     {

       make_pair((p[i].first+p[j].first)>>,(p[i].second+p[j].second)>>),

       1LL*(p[i].first-p[j].first)*(p[i].first-p[j].first)+

         1LL*(p[i].second-p[j].second)*(p[i].second-p[j].second), i,j

     };

     sort(vec+,vec+tot+);

     long long Ans=;

     for(int i=;i<=tot;++i)

     {

         int l=i,r; while(vec[i]==vec[i-])i++; r=i-;

         for(int j=l;j<=r;++j) for(int k=l;k<j;++k)

         {

             long long temp=(long long)(Dis(vec[j].x,vec[k].x)*

                 Dis(vec[j].x,vec[k].y)+0.5);

             if(temp>Ans)Ans=temp;

         }

     }

     printf("%lld\n",Ans/);

     return ;

 }

巴特西

[bzoj1356]Rectangle[Baltic2009][几何常识乱搞]

最新文章

热门文章