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 100100 501 150 90 250 52030 120

Sample Output

50000.0080100.00

Hint

题意：

　　　　给你一个二维的坐标系，你要从[0,0]走到[x,y]。但是其间会有一些平行于y轴的河，你需要架桥。给你每米的修路费，和每米的修桥费，问最少的费用是多少？

题解：

　　　　现场的时候看了这题，感觉是2元方程，很难求的感觉。赛后，师兄说是三分求最值。然后学了一下三分，就A了。

　　　　因为河全部是平行的，可以将河全部移动到一边，就可以变成一边是河，一边是陆地。

　　　　河的宽为：riverlen = 每一条和的宽度相加。陆地的宽为：landlen = x - riverlen。

　　　　设点[riverlen, yi]这个点时，费用最小。[0, 0]到[riverlen, yi]为桥的费用，陆地的费用同理。

看了一下别人的代码，发现了一个hypot()函数;

查了一个是一个求直角三角形的斜边的函数　　double hypot(double x, double y)。新知识:D，开心XD。

还有最主要就是三分的思想，到时会补一个三分详解。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
              8 #include 
              
                9 #include 
               
                10 #include 
                
                 11 #include 
                 
                  12 #include 
                  
                   13 using namespace std;14 #define pb push_back15 #define mp make_pair16 #define exp 1e-717 #define ms(a, b) memset((a), (b), sizeof(a))18 //#define LOCAL19 typedef long long LL;20 const int inf = 0x3f3f3f3f;21 const int maxn = 200000+10;22 const int mod = 1000000007;23 double n, x, y, c1, c2, riverlen, landlen;24 double cut(double hh)25 {26 return c2*hypot(riverlen, hh) + c1*hypot(landlen, y-hh);27 }28 int main() {29 #ifdef LOCAL30 freopen("input.txt" , "r", stdin);31 #endif // LOCAL32 while(~scanf("%lf%lf%lf%lf%lf", &n, &x, &y, &c1, &c2)){33 riverlen = 0.0;34 for(int i=0;i

View Code

转载于:https://www.cnblogs.com/denghaiquan/p/6741544.html

你可能感兴趣的文章