[ZJ][][代值解] b064. 3. 下界函＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2012-09-22 17:29:59| 人945| 回0 | 上一篇 | 下一篇

[ZJ][][代值解] b064. 3. 下界函

推 0 收藏 0 0 站台

容：

很久以前，喜研究字的家一有趣又用的，Davenport-Schinzel 。一足以下3 件：

1. 的任何一字都小於或等於一定的正整n
2. 任意相的字都一
3. 找到字隔地出s+2 次以上(包含s+2 次)

就 (n, s) Davenport-Schinzel ， DS(n, s) 。如， (1, 2, 3, 1, 3, 2, 1) 是一 DS(3, 3) ，我中取出 1 和 2 字得到 (1, 2, 1, 2, 1)，字隔地出5 次，所以它反第3 件。而 (1, 2, 3, 1, 3, 2, 3) 就是一 DS(3, 3) 。
Davenport-Schinzel 的性有多重要的用，其中之一就是用估算一性函 (linear functions) 之下界函 (lower envelope) 的段目。假 f₁, f₂, …, f_n 是一性函，每一 f_i 都代表一段，它的下界函 L 的
定如下:

L(x) = min{f_i(x) | 1 ≤ i ≤ n}

其中 L 的定域 (domain) 是所有 f_i 之定域的集。如果 f₁, f₂, …, f_n 的定域都相同的，L 是一凸包(convex)形的函，如一(a)；否 L 可能是的段，如一(b)。注意，在一(b)中x∈(x₁, x₂) 包含在L 的定域中。

用 Davenport-Schinzel 估算下界函式的段，需要很的
算。你用程式忙算一函的下界函包含有多少段。在
，你可以假任 f_i 和 f_j 有重或相接成一段的情形，
且入中也有垂直的存在。

入明：

中一(a)和一(b)的情形都有可能出。的第一一正整n (1 ≤ n ≤ 500)，代表有 n 函。接下的 n ，每有四介於 0 到10000 的整x₁、y₁、x₂、y₂，代表一端 (x₁, y₁) 和 (x₂, y₂) 的段函
。

出明：

出下界函所包含的段，每一。如一(a) 出 3，一(b)
出 7。

例入：

4 0 100 100 20 0 20 100 80 0 40 100 50 0 70 100 60 5 0 30 50 30 40 20 70 15 10 20 30 40 80 10 120 40 90 0 110 40

例出：

3 7

提示：

出：

94全科能力

做法 : 代 x 值, 找不同的
由於是格子, 那只好一, 因段相交之後又要拆段有於麻,
於是定代值判, 因是格子, 那交可能位於不是格子的部分, +1 可能有差,
因此 x 每次增加 0.5

#include <stdio.h>
typedef struct {
    int xr, xl, yr, yl;
} seg;
int main() {
    int n, i, j;
    seg D[500];
    while(scanf("%d", &n) == 1) {
        int tmp;
        int l = 0xfffff, r = 0;
        for(i = 0; i < n; i++) {
            scanf("%d %d %d %d", &D[i].xl, &D[i].yl, &D[i].xr, &D[i].yr);
            if(D[i].xl > D[i].xr) {
                tmp = D[i].xl, D[i].xl = D[i].xr, D[i].xr = tmp;
                tmp = D[i].yl, D[i].yl = D[i].yr, D[i].yr = tmp;
            }
            if(D[i].xl < l) l = D[i].xl;
            if(D[i].xr > r) r = D[i].xr;
        }
        int prev = -1, used;
        int ans = 0;
        double x;
        for(x = l; x <= r; x += 0.5) {
            used = -1;
            double val = 0xfffff, tmp;
            for(j = 0; j < n; j++) {
                if(D[j].xl <= x && D[j].xr >= x) {
                    tmp = D[j].yl - (double)(D[j].yl-D[j].yr)*(D[j].xl-x)/(D[j].xl-D[j].xr);
                    if(tmp < val) {
                        val = tmp;
                        used = j;
                    }
                }
            }
            if(used == -1) continue;
            if(used != prev) {
                prev = used;
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}