注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2338(hnoi2011)数矩形  

2013-02-21 22:03:55|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

有n个点,那么就有n^2个线段

如果有两条线段中点坐标相同,长度相等,一个矩形就构造出来咯

然后算面积……我各种画图希望能得到一个简单的、不需要用到实数的、正确的、没有特殊情况的、让自己有成就感的公式

然后就因此在这道题上花了好多时间啊!!

所以我再也受不了了两点间距离公式计算长宽再相乘,呃,用到了实数,没有成就感……不过简单啊,不过正确啊啊,不过没有特殊情况啊啊啊啊

 

有人说如果有x条线段中点坐标都相同,长度都相等,怎么办嘞?

有人说:“利用XX单调性XXXX一下再YY一下然后就线性的搞出来了”。不过我不会……

有人说:“x^2爆搞不就可以了撒,数据又很难卡。”其实不难我所有点都重合不就卡死了不就变成n^4了…………

所以我就加了个无聊的剪枝:用个set判重,如果有多个点重合就只算作一个,然后再x^2爆搞。那么那个所有点都重合的“极限数据”就缩水了

所以我的程序因为用了set而变得比别人x^2还慢了…………囧囧囧囧囧

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#define MAXN 1510
#define MAXM 1250000
using namespace std;
typedef long long LL;
int n,m;
double ans;
struct Point
{
    LL x,y;
    Point() {}
    Point(LL x,LL y): x(x),y(y) {}
    friend Point operator - (const Point &a,const Point &b){  return Point(a.x-b.x,a.y-b.y);  }
    friend Point operator + (const Point &a,const Point &b){  return Point(a.x+b.x,a.y+b.y);  }
    friend bool operator < (const Point &a,const Point &b){  return a.x<b.x||(a.x==b.x&&a.y<b.y);  }
    friend bool operator == (const Point &a,const Point &b){  return a.x==b.x&&a.y==b.y;  }
    void Read(){  scanf("%lld %lld",&x,&y);  }
}p[MAXN];
typedef Point Vector;
LL Dot(const Vector &a,const Vector &b){  return a.x*b.x+a.y*b.y;  }
double Len(const Vector &a){  return sqrt(Dot(a,a));  }
set<Point>hash;
struct Seg
{
    Point l,r,mid2;
    LL len2;
    friend bool operator < (const Seg &a,const Seg &b){  return a.mid2<b.mid2||(a.mid2==b.mid2&&a.len2<b.len2);  }
}L[MAXM];
void read()
{
    scanf("%d",&n);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        Point a;
        a.Read();
        if(hash.count(a))  continue;
        hash.insert(a),p[++cnt]=a;
    }
    n=cnt;
}
void work()
{
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            ++m,L[m].l=p[i],L[m].r=p[j],L[m].mid2=p[i]+p[j],L[m].len2=Dot(p[i]-p[j],p[i]-p[j]);
            if(p[j]<p[i])  swap(L[m].l,L[m].r);
        }
    sort(L+1,L+m+1);
    for(int i=1;i<=m;i++)
        for(int j=i-1;j>=1&&L[j].mid2==L[i].mid2&&L[j].len2==L[i].len2;j--)
            ans=max(ans,Len(L[i].l-L[j].l)*Len(L[i].l-L[j].r));
}
int main()
{
    read();
    work();
    printf("%.0lf\n",ans);
    return 0;
}


  评论这张
 
阅读(427)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017