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

n+e

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

 
 
 

日志

 
 

[BZOJ1278]向量vector  

2015-01-29 11:04:03|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1278: 向量vector

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 177  Solved: 30
[Submit][Status]

Description

一个二维向量(x,y)的权定义为x2+y2。已知一个由n个二维向量组成的集合,求该集合的一个子集,使该子集中的向量和的权尽可能大。

Input

第1行一个数n,表示n个向量。 下面n行,每行2个实数,表示n个向量。

Output

1个实数,即向量和最大的权。(精确到小数点后3位)

Sample Input

3
1 1
1 0
0 -1

Sample Output

5.000

HINT

n<=100000

Solution

有一个结论是,构成答案的向量一定在某一个过原点的直线一侧,证明的话可以将这些向量首尾相接,组成一个类似半圆的东西,离远点比较远。

//其实输入数据都是整数,在最后输出答案的时候加一个".000"就好了

Code

/**************************************************************
    Problem: 1278
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1672 ms
    Memory:5508 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ld long long
struct P{ld x,y;};
#define PP const P&
P operator+(PP a,PP b){return (P){a.x+b.x,a.y+b.y};}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
ld cross(PP a,PP b){return a.x*b.y-a.y*b.x;}
ld len2(PP x){return x.x*x.x+x.y*x.y;}
ld aa;ld F(){return scanf("%lld",&aa),aa;}
bool cmp(PP a,PP b){
    if(a.x==b.x&&a.y==b.y)return 0;
    return atan2(a.y,a.x)<atan2(b.y,b.x);
}
ld max(ld a,ld b){return a>b?a:b;}
int n,i,j,k,m;P a[200010],now,tmp,b[100010];ld ans;
int main()
{
    for(n=F(),i=1;i<=n;i++)a[i]=(P){F(),F()};
    std::sort(a+1,a+1+n,cmp);
    for(i=1;i<=n;i++)a[i+n]=a[i];
    for(i=j=1,now=a[1];i<=n;i++){
        while(j+1<i+n&&cross(a[i],a[j+1])>=0)now=now+a[++j],ans=max(ans,len2(now));
        now=now-a[i];
        ans=max(ans,len2(now));
    }
    printf("%lld.000\n",ans);
}
  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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