想吃冰卻又敏感保護不足?直擊★美車模手癢不小心...法人:14檔今年本業虧定了破戒!比丘吃葷 連3次...
2013-01-04 15:39:41 人氣(103) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][掃描線] 972 - Horizon Line

0
收藏
0
推薦


Problem A - Horizon Line

Let f(x) and g(x) be two functions defined in the same domain [a,b]. The horizon line corresponds to the function that presents, in each point x, the maximum value from both original functions: h(x)=Max(f, g).


Figure 1 - Construction of a horizon function

The maximum value of h(x) can be directly obtained from the both functions maxima, so it wouldn't make it necessary to determine the horizon line. Nevertheless, the same is not true for the minimum value of h(x) that has to be evaluated through a more complex method.

The Problem

Your task for this problem is to evaluate the minimum value of a horizon line h(x), given two functions f(x) and g(x). To make it easier, both initial functions are composed by different steps like the dotted lines represented in figure 1, but x and y values are not necessarily integer values. Each function is composed by a sequence of N steps, with each step being defined by a length and a value. It is ensured that the last step ends at the domain upper limit and the domain is always [0,10].

Input

The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.

The input is made of two sequences of text lines, representing the functions f and g.

In each sequence, the first line contains the number of the function steps N (integer format); it is followed by N lines containing, each one, the step value and the step length (by this order, in decimal format) separated by one or more spaces. It is ensured that a sequence has no more than 100 steps.

Output

For each test case, the output is made of one text line containing the minimum value of the horizon line h(x). It must be rounded to three decimal digits.

Example Input

4
6.0 2.0
1.0 3.0
3.0 1.0
5.0 4.0
3
4.0 4.0
8.0 4.0
1.0 2.0

Example Output

4.000

2006 Programming Contest of Porto University
Round 3, 11th of October of 2006
 
(Author: Augusto Sousa - FEUP)


求 h(x) 的最小值,而 h(x) = max(f(x), g(x))

#include <stdio.h>
#include <algorithm>
using namespace std;
struct LINE {
    double st, ed, y;
};
int main() {
    int n, m;
    while(scanf("%d", &n) == 1) {
        double a, b, sum;
        double P[500];
        LINE F[105], G[105];
        int cnt = 0, i;
        for(i = 0, sum = 0; i < n; i++) {
            scanf("%lf %lf", &a, &b);
            F[i].st = sum, F[i].ed = sum+b;
            F[i].y = a;
            P[cnt++] = sum, P[cnt++] = sum+b;
            sum += b;
        }
        scanf("%d", &m);
        for(i = 0, sum = 0; i < m; i++) {
            scanf("%lf %lf", &a, &b);
            G[i].st = sum, G[i].ed = sum+b;
            G[i].y = a;
            P[cnt++] = sum, P[cnt++] = sum+b;
            sum += b;
        }
        double res = 1e+10;
        sort(P, P+cnt);
        int pf = 0, pg = 0;
        for(i = 0; i < cnt; i++) {
            while(F[pf].ed < P[i])  pf++;
            while(G[pg].ed < P[i])  pg++;
            res = min(max(F[pf].y, G[pg].y), res);
        }
        printf("%.3lf\n", res);
    }
    return 0;
}

972Horizon Line
台長:Morris
人氣(103) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: ���分類 | 個人分類: UVA |
此分類下一篇:[UVA][幾何] 10613 - Mushroom Misery
此分類上一篇:[UVA][Trie][大數] 12333 - Revenge of Fibonacci

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文