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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1765/2338/1356][Baltic2009]rectangle  

2014-12-11 21:34:30|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description

给定平面上(N <= 1500)个草莓的坐标,都是整数,没有两个草莓重合。现在郑爽要选出4个草莓,构成一个矩形,这样才能和翰哥哥一起玩“爱的华尔兹“。为了更浪漫,爽妹还要这个矩形面积最大。

Input

第一行为一个整数N 接下来N行,每行两个数代表坐标,绝对值小于等于10^8

Output

一个整数代表爽妹想要的最大的矩形面积。

Sample Input

8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1

Sample Output

10

Solution

n^2把每条直线搞出来,记下它的端点、长度、中点。然后按中点排序。中点相同的按距离排序。在两者都相同的情况下用平方级别的算法暴力更新答案。

似乎会T,但是由于端点坐标都是整数,然后以某个点为圆心,半径为正整数的圆经过的整数点其实不会太多,所以就放心写吧~

Code

/**************************************************************
    Problem: 1765
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:3336 ms
    Memory:35992 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
int aa,bb;char ch;int F(){
    while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return bb?aa:-aa;
}
struct P{ll x,y;}a[1510];
P operator+(const P&a,const P&b){return (P){a.x+b.x,a.y+b.y};}
P operator-(const P&a,const P&b){return (P){a.x-b.x,a.y-b.y};}
ll l2(const P&a){return a.x*a.x+a.y*a.y;}
bool operator<(const P&i,const P&j){return i.x<j.x||i.x==j.x&&i.y<j.y;}
struct L{P p;int x,y;ll d;}l[1125010];
bool operator<(const L&i,const L&j){return i.d<j.d||i.d==j.d&&i.p<j.p;}
int n,i,j,tot,r,s;ll ans;
ll cross(const P&a,const P&b){return std::abs(a.x*b.y-a.y*b.x);}
#define calc(a,b,c) (cross(b-a,c-a))
void getans(int x,int y){
    for(r=x;r<=y;r++)
    for(s=x;s<r;s++)
    ans=std::max(ans,calc(a[l[r].x],a[l[s].x],a[l[s].y]));
}
int main(){
    for(n=F(),i=1;i<=n;i++)a[i]=(P){F(),F()};
    for(std::sort(a+1,a+1+n),i=1;i<=n;i++)
    for(j=1;j<i;j++)l[++tot]=(L){a[i]+a[j],j,i,l2(a[i]-a[j])};
    for(std::sort(l+1,l+1+tot),i=1;i<=tot;getans(i,j-1),i=j)
    for(j=i+1;l[i].d==l[j].d&&l[i].p.x==l[j].p.x&&l[i].p.y==l[j].p.y;j++);
    printf("%lld\n",ans);
}

  评论这张
 
阅读(125)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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