纪中10日 2313. 动态仙人掌 

(File IO): input:dinosaur.in output:dinosaur.out

时间限制: 

1500 ms  空间限制: 524288 KB  具体限制  

题目描述

沙雕游戏……反正我没玩过……

输入

输出

样例输入

数据范围限制

Solution

考试时想的是对的

为什么就是没有分呢？

首先看看仙人掌有几种情况

situation1

两个比较分开的仙人掌……

小恐龙按照这样走（跳），并没有什么特殊操作。这时的最高高度是两个仙人掌中最高的高度。

situation2

两个靠的比较近的仙人掌……

先看第一个，为了高度尽量小，当然选择擦边跳了

 

但是恐龙只有落地才能跳呀……要是它跳完第一个就落地，再起跳，一定会装上第二个仙人掌的！

所以它只能一次性的跳过两个仙人掌……

求最高点：

设第一个的高度为a，第二个的高度为b，两个之间的距离为c；

标点

解：

因为△ABC是直角等腰三角形

所以AD=DC=a

同理可得：

EG=FG=b

所以AF=AD+DG+GF=a+b+c

延长AB，EF，交于H点

△AHF亦为直角等腰三角形

所以AH=HF=AF/2=(a+b+c)/2

那么就可以把两个仙人掌合成一个更高的了

Code

#include
     
      //不想OI一场空，千万别用万能头#include
      
       //快排sort()#include
       
        //能不用cin就不用#include
        
         #include
         
        
       
      
     

 

Code std

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct cly{    int longn,left,right;}a[300100];double ans;int n,p[300100],h[300100],l,r,i;bool cmd(cly x,cly y){    return x.left
         
          >n;    for(i=1;i<=n;i++)    {        scanf("%d%d",p+i,h+i);        a[i]=(cly){h[i],p[i]-h[i],p[i]+h[i]};    }    sort(a+1,a+1+n,cmd);    if(a[1].left<0)    {        cout<<"-1";        return 0;    }    l=a[1].left;    r=a[1].right;    i=1;    while(i
          
           =a[i+1].right) { i++; } else { i++; r=a[i].right; } } ans=max(ans,1.0*(r-l)/2); printf("%.1lf",ans); return 0;}