首页 > ACM题库 > HDU-杭电 > HDU 4816-Bathysphere-模拟-[解题报告]HOJ
2015
09-18

HDU 4816-Bathysphere-模拟-[解题报告]HOJ

Bathysphere

问题描述 :

The Bathysphere is a spherical deep-sea submersible which was unpowered and lowered into the ocean on a cable, and was used to conduct a series of dives under the sea. The Bathysphere was designed for studying undersea wildlife.

The Bathysphere was conducted from the deck of a ship. After counted, the ship should not move, so choosing the position where the Bathysphere was conducted is important.

A group of scientists want to study the secrets of undersea world along the equator, and they would like to use the Bathysphere. They want to choose the position where the Bathysphere can dive as deep as possible. Before conducting the Bathysphere, they have a map of the seabed, which tell them the shape of the seabed. They draw a line on the equator of the map to mark where they will release the Bathysphere, as a number axis. Suppose the axis is draw from 0 to L. But when they release the Bathysphere, they can’t know where they are accurately, i.e., if they choose position x to release the Bathysphere, the real position will distribute between x-d and x+d with an equal probability, where d is given. The objective of the scientists is very simple, i.e., to maximize the expected depth.

For the ease of presentation, the shape of the seabed is described as a poly line. Given N points ) , ( Xi,Yi ) as the vertices, where Xi and Yi indicate the position and the depth of the i-th vertex, respectively, the ploy line is composed of the line segments that connect consecutive vertices.

输入:

The first line contains an integer T (1 ≤ T ≤ 25), the number of test cases.

Then T test cases follow. In each test case, the first line contains two integers N (2 ≤ N ≤ 2*10^5) and L (2 ≤ L ≤ 10^9), as described above. Then N lines follow, each line contains two integer Xi and Yi (1≤i≤N, 0≤ Yi ≤10^9), where point ( Xi,Yi ) is a vertex of the ploy line. It is assumed that X1 == 0 and Xn == L and Xi < Xi+1 for 1 ≤ i < N. Then the following line contains one integer d (0 ≤ d ≤ L/2), as described above.

输出:

The first line contains an integer T (1 ≤ T ≤ 25), the number of test cases.

Then T test cases follow. In each test case, the first line contains two integers N (2 ≤ N ≤ 2*10^5) and L (2 ≤ L ≤ 10^9), as described above. Then N lines follow, each line contains two integer Xi and Yi (1≤i≤N, 0≤ Yi ≤10^9), where point ( Xi,Yi ) is a vertex of the ploy line. It is assumed that X1 == 0 and Xn == L and Xi < Xi+1 for 1 ≤ i < N. Then the following line contains one integer d (0 ≤ d ≤ L/2), as described above.

样例输入:

2
3 10
0 3
4 10
10 1
5
3 10
0 3
4 10
10 1
1

样例输出:

5.900
9.192

今天模拟了去年长春Regional。
我们队居然做到了五题,20名左右的样子。
可惜最后一个小时开两道题都没做出来。

这题是其中之一:
给你n个点,相邻点连线,求一段长d区间的高度期望最大值。

算法如下:
高度是就是面积除以区间长度。
这样就是求面积的最大值。
面积的二阶导数是斜率,定值。因此可用三分法求极值。
枚举所有给定的点作为左端点或右端点,在到下一个端点之间一段区间内做三分求最大值即可。

听说现场赛卡三分。。求导可以直接求出极值。哎数学弱就要被吊打……

三分代码,G++可以过,C++会T哟。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Maxn 200100
#define eps 1e-8

inline double getarea(double hk,double hy,double tk,double ty,double len){
    return (ty+ty+len*tk)*len/2.0-(hy+hy+len*hk)*len/2.0;
}

void work(double nowarea,double hk,double hy,double tk,double ty,double tlen,double &ans){
    double l=0,r=tlen,ll,rr,tmp,al,ar;
    while(r-l>eps){
        ll=(l+l+r)/3.0;
        rr=(l+r+r)/3.0;
        al=getarea(hk,hy,tk,ty,ll);
        ar=getarea(hk,hy,tk,ty,rr);
        if (al<ar) l=ll;
        else r=rr;
    }
    tmp=getarea(hk,hy,tk,ty,l);
    if (nowarea+tmp>ans) ans=nowarea+tmp;
}

int x[Maxn],y[Maxn];
double area[Maxn];

int main(){
    //freopen("din.txt","r",stdin);
    int cas,n,l,may,d,i;
    int nh,nt;
    double headx,heady,tailx,taily,kh,kt,tmpl,nowarea,ans;
    double len1,len2;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&n,&l);
        may=0;
        for(i=1;i<=n;++i){
            scanf("%d%d",&x[i],&y[i]);
            if (y[i]>may) may=y[i];
        }
        x[n+1]=l+1;
        y[n+1]=y[n]+1;
        scanf("%d",&d);
        if (d==0) {printf("%.3lf\n",may);continue;}
        d=2*d;
        area[0]=area[1]=0;
        for(i=2;i<=n;++i){
            area[i]=area[i-1]+((double)y[i-1]+y[i])*((double)x[i]-x[i-1])/2.0;
        }
        for(i=1;i<=n;++i){
            if (d>=x[i]&&d<x[i+1]) {break;}
        }
        nh=2;nt=i+1;
        kh=((double)y[2]-y[1])/((double)x[2]-x[1]);
        kt=((double)y[nt]-y[nt-1])/((double)x[nt]-x[nt-1]);
        headx=x[1],heady=y[1];
        tailx=d;taily=y[nt-1]+kt*(d-x[nt-1]);
        nowarea=ans=area[nt-1]+(d-x[nt-1])/2.0*(y[nt-1]+y[nt-1]+kt*(d-x[nt-1]));
        while(1){
            if (tailx+eps>=l) break;
            len1=x[nh]-headx;
            len2=x[nt]-tailx;
            if (len1<len2) tmpl=len1;
            else tmpl=len2;
            work(nowarea,kh,heady,kt,taily,tmpl,ans);
            nowarea=nowarea+getarea(kh,heady,kt,taily,tmpl);
            if (len1<len2){
                headx=x[nh];
                heady=y[nh];
                tailx+=tmpl;
                taily+=kt*tmpl;
                nh+=1;
                kh=((double)y[nh]-y[nh-1])/((double)x[nh]-x[nh-1]);

            }
            else{
                headx+=tmpl;
                heady+=kh*tmpl;
                tailx=x[nt];
                taily=y[nt];
                nt+=1;
                kt=((double)y[nt]-y[nt-1])/((double)x[nt]-x[nt-1]);
            }
        }
        printf("%.3lf\n",ans/(1.0*d));
    }
    return 0;
}


参考:http://blog.csdn.net/asdfgh0308/article/details/38881287