[UVA][掃描線] 972 - Horizon Line
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;
}