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

n+e

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

 
 
 

日志

 
 

[BZOJ2458][BeiJing2011]最小三角形  

2015-01-29 13:06:31|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2458: [BeiJing2011]最小三角形

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 679  Solved: 217
[Submit][Status]

Description

Xaviera现在遇到了一个有趣的问题。
平面上有N个点,Xaviera想找出周长最小的三角形。
由于点非常多,分布也非常乱,所以Xaviera想请你来解决这个问题。
为了减小问题的难度,这里的三角形也包括共线的三点。

Input

第一行包含一个整数N表示点的个数。
接下来N行每行有两个整数,表示这个点的坐标。

Output

输出只有一行,包含一个6位小数,为周长最短的三角形的周长(四舍五入)。

Sample Input

4
1 1
2 3
3 3
3 4

Sample Output

3.414214

HINT

100%的数据中N≤200000。

Solution

正解是分治,类似于平面内最近点对的做法。

让我们乱搞A掉这题吧:将坐标系随机旋转,并按照xy坐标排序。对于每个点,如果只扫它附近的几个点,有很大概率会出现答案。

扫附近12个点就够了,然后就是暴力。

Code

/**************************************************************
    Problem: 2458
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2620 ms
    Memory:3936 kb
****************************************************************/
 
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<algorithm>
struct P{double x,y;}z,b[200010];int n,k,l;double ans=1e10,tmp,t;
bool operator<(const P&a,const P&b){return a.x<b.x||(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};}
P operator-(const P&a,const P&b){return (P){a.x-b.x,a.y-b.y};}
P operator*(const P&a,double p){return (P){a.x*p,a.y*p};}
P operator*(const P&a,const P&b){return (P){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
double len(const P&a){return sqrt(a.x*a.x+a.y*a.y);}
int main()
{
    scanf("%d",&n);int i,j;k=10;srand(19980301);
    for(i=1;i<=n;i++)scanf("%lf%lf",&b[i].x,&b[i].y);
    t=rand();z=(P){cos(t),sin(t)};
    for(i=1;i<=n;i++)b[i]=b[i]*z;
    std::sort(b+1,b+1+n);
    for(i=1;i<n;i++)
    for(j=i+1;j<i+k&&j<n;j++)
    for(l=j+1;l<=i+k&&l<=n;l++)
    {
        tmp=len(b[l]-b[i])+len(b[j]-b[i])+len(b[l]-b[j]);
        if(ans>tmp)ans=tmp;
    }
    printf("%.6lf\n",ans);
}
  评论这张
 
阅读(40)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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