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

n+e

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

 
 
 

日志

 
 

[BZOJ3707][FJSC2014]圈地  

2014-07-20 21:00:01|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3707: 圈地

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 110  Solved: 37
[Submit][Status][Discuss]

Description

2维平面上有n个木桩,黄学长有一次圈地的机会并得到圈到的土地,为了体现他的高风亮节,他要使他圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形,多边形的顶点就是一个木桩,圈得的土地就是这个多边形内部的土地。(因为黄学长非常的神,所以他允许圈出的第n点共线,那样面积算0)

Input

第一行一个整数n,表示木桩个数。
接下来n行,每行2个整数表示一个木桩的坐标,坐标两两不同。

Output

仅一行,表示最小圈得的土地面积,保留2位小数。

Sample Input

3 0 0 0 1 1 0

Sample Output

0.50

HINT

对于100%的数据,n<=1000。

Solution

这题被我乱搞搞掉了= =

暴力n^3不多说。但是有很多时候的情况是没有用的。于是我们把这些点分成sqrt(n)块,块内暴力,轻松愉快。

这样做不靠谱,所以我们可以随机旋转坐标系,rand个四五十次就可以把这题水过了。

 

出题人题解:

  显然,这时候暴力枚举会T。于是我们转变一下思路,如果我们确定了2个点以后,第三个点有必要去盲目的枚举吗?答案是否定的。实际上我们把经过这两点的线看成一个斜率,把他当成y轴你会发现第三个点明显是在坐标系左右找一个离”y”最近的点来算面积更新答案。然后我们可以继续思考,发现我们可以把点按照某个斜率当成”y”进行“从左到右”的排序,这样当2点共线的时候,用这两个点的左右2个点去更新答案就好了。也就是说我们采用旋转坐标系的方法,一开始按x坐标排好序,认为直接用竖着的那条斜率,然后维护的话每次其实当两点共线后只要交换他们就能得到斜率转过该事件点的序列。所以我们可以预处理出所有可行的斜率,当成事件点,不断转动坐标系更新答案就好。这样复杂度只有n^2,期望得分100.(这确实只是个暴力的优化 啊。。。不要砸我T_T)

(好像很复杂的样子。。。不过也还好就是了)

Code

/**************************************************************
    Problem: 3707
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:424 ms
    Memory:848 kb
****************************************************************/
 
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<algorithm>
const double pi=3.1415926535897932384626;
struct P{double x,y;}a[1010],z,b[1010];int n,k;double ans=1e10,tmp,t;
bool operator<(P const&a,P const&b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
P operator+(P const&a,P const&b){return (P){a.x+b.x,a.y+b.y};}
P operator-(P const&a,P const&b){return (P){a.x-b.x,a.y-b.y};}
P operator*(P const&a,double p){return (P){a.x*p,a.y*p};}
P operator*(P const&a,P const&b){return (P){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
double cross(P const&a,P const&b){return a.x*b.y-a.y*b.x;}
double dot(P const&a,P const&b){return a.x*b.x+a.y*b.y;}
int main()
{
    scanf("%d",&n);int i,j;k=(int)sqrt(n)+10;/*srand(time(0));*/
    for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
    int p1=31,p2=23;
    for(int tt=1;tt<=p1;tt++)
    {
        z=(P){cos(pi/p2*tt),sin(pi/p2*tt)};
        for(i=1;i<=n;i++)b[i]=a[i]*z;
        std::sort(b+1,b+1+n);
        for(int kk=1;(kk-1)*k<=n;kk++)
        for(i=(k*(kk-1)+1);i<n&&i<k*kk;i++)
        for(j=i+1;j<n&j<k*kk;j++)
        for(int l=j+1;l<=n&&l<k*kk;l++)
        {
            tmp=std::abs(cross(b[l]-b[i],b[j]-b[i]));
            if(ans>tmp)ans=tmp;
        }
    }
    printf("%.2lf\n",ans/2.0);
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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