当前位置:首页 > 综合 > 综合

csu 1548: Design road(3分)

优良自学吧提供csu 1548: Design road(3分),csu 1548: Design road(三分) 1548: Design road Time Limit: 2 Sec  Memory Limit: 256 MB Submit: 243  Solved: 115 [Submit][Status][Web Board]

csu 1548: Design road(三分)

1548: Design road

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 243  Solved: 115
[Submit][Status][Web Board]

Description

You need to design road from (0, 0) to (x, y) in plane with the lowest cost. Unfortunately, there are N Rivers between (0, 0) and (x, y).It costs c1 Yuan RMB per meter to build road, and it costs c2 Yuan RMB per meter to build a bridge. All rivers are parallel to the Y axis with infinite length.

Input

There are several test cases.
Each test case contains 5 positive integers N,x,y,c1,c2 in the first line.(N ≤ 1000,1 ≤ x,y≤ 100,000,1 ≤ c1,c2 ≤ 1000).
The following N lines, each line contains 2 positive integer xi, wi ( 1 ≤ i ≤ N ,1 ≤ xi ≤x, xi-1+wi-1 < xi , xN+wN ≤ x),indicate the i-th river(left bank) locate xi with wi width.
The input will finish with the end of file.

Output

For each the case, your program will output the least cost P on separate line, the P will be to two decimal places .

Sample Input

1 300 400 100 100
100 50
1 150 90 250 520
30 120

Sample Output

50000.00
80100.00

HINT


题意:修路:从(0,0)~(x,y)n个数表示有第二行开始有n行表示有n条河,tx是河的起始位置,ty是河的宽度,有水的地方要修桥,而xy表示修路的端点,C1表示修路每米的花费,C2表示修桥每米的花费,问你最后花费的最少金额!

题解:吧河移到靠 x 处,然后left =0,right =y,三分,求极小值。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define eps 1e-8

int n;
double x,y,c1,c2,W;

double ff(double ay) {
    return sqrt((x-W)*(x-W)+ay*ay)*c1+sqrt((y-ay)*(y-ay)+W*W)*c2;
}

int main() {
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%lf%lf%lf%lf",&n,&x,&y,&c1,&c2)) {
        double ax,aw;
        W=0;
        for(int i=0; i<n; i++) {
            scanf("%lf%lf",&ax,&aw);
            W+=aw;
        }
        double left=0,right=y*1.0;
        double mid1,mid2;
        for(int i=0; i<100; i++) {
            mid1=(right+left)/2;
            mid2=(left+mid1)/2;
            if(ff(mid1)<ff(mid2)) {
                left=mid2;
            } else {
                right=mid1;
            }
        }
        printf("%.2f\n",ff(left));
    }
    return 0;
}



(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢