hdu_4368 Water World I (计算几何)

题意：
给出n个柱子一字排开,并且整体倾斜angle角度.向左为正,向右为负.求最多的积水量。
思路:
找出倾斜后最高柱子，再分求再边的水。有个小trick，水位刚好在某柱子中间：
以下来自官解题报告：
为使考虑简单,当angle为负时,将n个柱子颠倒顺序,angle取绝对值,得到的结果实际上是一样的.因此只需考虑向左倾斜
同时,为了避免大量坐标变换,柱子倾斜,其实就是地平线/水平面倾斜,因此,柱子不变,柱子左下角设为原点.从原点往右下角拉一条线出来作为倾斜的地平线.
接下来,计算每根柱子顶端与地平线的最大垂直距离.那么,水体肯定在2根距离较高的,柱子中间.称这2根柱子匹配
找到距离最大的柱子,那么,对于左侧的柱子,肯定与右边最近的,与地平线距离大于等于本身的柱子相匹配.对于右侧的柱子,肯定与左边某柱子匹配.因此做向左向右两次循环即可找出所有匹配.
我的代码：
[cpp]
/*
program:hdu_4368
author:BlackAndWhite
*/ 
#include<stdio.h> 
#include<math.h> 
#define eps 1e-5 
#define PI 3.1415926535897932384626 
int n,a[10001]; 
double angle; 
int i,j,k,maxtop; 
double dis[10001],t,top,ans,low,h; 
int main() 
{ 
    while(~scanf("%d%lf",&n,&angle)) 
    { 
        if(angle<-eps) for(i=n-1;i>=0;i--) scanf("%d",&a[i]); 
        else for(i=0;i<n;i++) scanf("%d",&a[i]); 
        if(angle<-eps) angle=-angle;//只考虑向左倾斜  
        angle=PI*angle/180.0; 
        t=-1;ans=0; 
        for(i=0;i<n;i++) 
        { 
            dis[i]=((i+1)*tan(angle)+a[i]*1.0)/sqrt(tan(angle)*tan(angle)+1); 
            if(t<dis[i]){t=dis[i];maxtop=i;}//找离地面最高的柱子  
        } 
        for(i=0;i<maxtop;i++)//最高柱子的前面  
        { 
            top=a[i]; 
            for(j=i+1;j<=maxtop;j++) 
            { 
                if(dis[j]>dis[i]+eps) 
                { 
                    if(dis[j]-sin(angle)>dis[i]+eps) 
                    { 
                        top-=(j-i-1)*1.0*tan(angle); 
                        ans+=(j-i-1)*(j-i-1)*0.5*tan(angle); 
                    } 
                    else//trick，水刚好某个柱子了中间  
                    { 
                        top-=(a[i]-a[j])*1.0; 
                        ans+=(a[i]-a[j])*(a[i]-a[j])*0.5/tan(angle); 
                    } 
                    for(k=i+1;k<j;k++) 
                        ans+=(top-a[k])*1.0; 
                    i=j-1; 
                    break; 
                } 
            } 
        } 
        for(i=n-1;i>maxtop;i--)//右边，相对简单些，没有trick  
        { 
            for(j=i-1;j>=maxtop;j--) 
            { 
                    h=i-j; 
                    low=h*tan(angle)-(a[j+1]-a[i]); 
                    top=(h-1)*tan(angle)-(a[j+1]-a[i]); 
                    ans+=(top+low)/2.0; 
                if(dis[j]>dis[i]+eps) 
                    break; 
            } 
            i=j+1; 
        } 
        printf("%.2lf/n",ans); 
    } 
    return 0; 
} 
作者：q411307827