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

n+e

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

 
 
 

日志

 
 

[BZOJ2033/1038][2009国家集训队]大灾变  

2015-03-27 18:56:33|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2033: [2009国家集训队]大灾变

Time Limit: 20 Sec  Memory Limit: 259 MB
Submit: 33  Solved: 11
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

3 2 0 1 10 3 10

Sample Output

1.00 10.00 2.00 0.00

HINT

Source

Solution

看完题目,“这不就是把可行域搞出来半平面交直接搞嘛?为什么A的人这么少?“
然后一看数据卧槽40组,然后翻一下题解就是这样啊= =
然后码完代码,交一发,Wa;本机cena,92.5
尼玛这叉的一手好数据。。。
细节比较多。比如不能输出-0.00,在做半平面交的时候记得插入最左边和最右边的两个半平面,......

Code

/**************************************************************
    Problem: 2033
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1844 ms
    Memory:35968 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
typedef double ld;ld now;
#define N 1000010
struct P{ld x,y;}a[N],p[N],tmp,ans1,ans2,tmp2;
#define PP const P&
bool operator<(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
bool cmp(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y>b.y;}
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};}
P operator*(PP a,PP b){ld d=a.x*b.x,e=a.y*b.y,f=(a.x+a.y)*(b.x+b.y);return (P){d-e,f-e-d};}
ld operator&(PP a,PP b){return a.x*b.y-a.y*b.x;}
ld check(PP a,PP b,PP c){return (b-a)&(c-a);}
int n,i,j,r,q[N];
P calc(PP a,PP b){
    ld k=(a.y-b.y)/(a.x-b.x);
    return (P){k,a.y-a.x*k};
}
P jd(PP a,PP b){
    ld x=-(a.y-b.y)/(a.x-b.x);
    return (P){x,a.x*x+a.y};
}
#define mk(x) (x<1e-5&&x>-1e-5?x=0:1)
#define fd 1e-6
int main(){
    ans1.y=ans2.y=now=1e100;
    for(n=F(),i=1;i<=n;i++)p[i]=(P){F(),F()};
    std::sort(p+1,p+1+n);
    for(i=1;i<n;i++)a[i]=calc(p[i],p[i+1]);
    a[n]=calc(p[1],p[1]+(P){-1e-5,1e5}),a[n+1]=calc(p[n],p[n]+(P){1e-5,1e5});
    std::sort(a+1,a+n+2,cmp);a[0].x=-1e100;
    for(i=1;i<=n+1;i++)if(a[i].x!=a[i-1].x){
        while(r>1&&check(a[q[r-1]],a[q[r]],a[i])>=0)r--;q[++r]=i;
    }
    for(i=j=1;i<r;i++){
        tmp=jd(a[q[i]],a[q[i+1]]);
        if(tmp.y<ans2.y&&ans2.y>fd)ans2=tmp;
        while(j<=n&&p[j].x<=tmp.x){
            if(p[j].x*a[q[i]].x+a[q[i]].y-p[j].y<now&&now>fd)
            now=p[j].x*a[q[i]].x+a[q[i]].y-p[j].y,ans1=(P){p[j].x,now+p[j].y};
            j++;
        }
        if(j<=n&&j>1){
            tmp2=calc(p[j-1],p[j]);
            if(tmp.y-(tmp.x*tmp2.x+tmp2.y)<now&&now>fd)
            now=tmp.y-(tmp.x*tmp2.x+tmp2.y),ans1=(P){tmp.x,tmp.y};
        }
    }
    mk(ans1.x),mk(ans1.y),mk(ans2.x),mk(ans2.y);
    printf("%.2lf %.2lf\n%.2lf %.2lf\n",ans1,ans2);
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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