大灾变 IOI2010国家集训队论文问题解析—— 河南省实验中学 郭家宝

Presentation on theme: "大灾变 IOI2010国家集训队论文问题解析—— 河南省实验中学 郭家宝"— Presentation transcript:

1 大灾变 IOI2010国家集训队论文问题解析—— 河南省实验中学 郭家宝
(click)大家好，我是河南省實驗中學的郭家寶，今天給大家帶來的問題解析的題目是：大災變(click) 河南省实验中学 郭家宝

2 问题回顾 有一座山脉，要求在山脉上建立一座瞭望塔，在山脉上空建立一个浮空岛，使得站在瞭望塔的顶端和浮空岛上，可以看到整个山脉。
瞭望塔塔身高度应尽量小，浮空岛的绝对海拔应尽量低，并且在满足上述条件的情况下横坐标尽量小。请你求出瞭望塔和浮空岛的坐标。 (read)(click)

3 问题回顾 样例如下图所示 瞭望塔 浮空岛 海平面
題中樣例如圖所示，瞭望塔建立在了一個山峰上，浮空島建立在瞭望塔右邊，在這兩個地方都可以看到整個山脈。(click)

4 欲窮千里目 更上一層樓 初步分析 题目要求看到整个山脉，就是看到所有的山坡。 首先考虑绝对高度最低点。
从一个较低高度开始垂直上升，直到看见整个山脉。 首先，一個點可以看到整個山脈，等價於這個點可以看到所有的山坡，又等價於這個點在所有山坡所在直線的上方。(click)由於山脈情況複雜，直觀上感覺第二問求絕對高度最低點會相對簡單，所以從這裡開始思考。(click)正如古詩“欲窮千里目，更上一層樓”所云，我們可以從一個較低的高度開始上升，直到看見為止。(click) 欲窮千里目 更上一層樓

5 行遠必自邇 登高必自卑 初步分析 站得越高，看得越远。 从低处向高处走，可视范围增加。 单调性。
但是僅僅“站得越高，看得越遠”是不夠的。如果我們站在一個很高的高度，那麼可以向下走一些，這樣才可能達到最優。(click) 我們找到了優美的“登高必自卑”的單調性。 行遠必自邇 登高必自卑

6 算法甲 二分枚举高度，判断当前高度上是否可以一览全貌。 如果存在，降低高度，如果不存在，升高高度。 如何判断？ ——登高必自卑
利用二分答案的枚舉高度，然後判斷此高度上是否有位置可以一覽山脈全貌。(click)由於存在“站得越高，看得越遠；站得越低，看得越近”的單調性，我們可以不斷縮小高度的查找區間，直到達到預期的精度。(click)可是如何判斷呢？問題就集中到了“如何判斷一個高度上是否有可以一覽全貌的位置”上。

7 算法甲 ——登高必自卑 可行区域 试探高度 海平面
給定一個高度以後，作在該試探高度上的水平線。山坡線所在直線上方一側就是可以看見該山坡的區域，這個區域映射到試探直線上，就是一個可視範圍的區間。我們將所有這些區間求交集，就是在該高度上可以看到山脈的區域。這樣，我們就解決了判定的問題。配合二分答案的方法，就是算法甲。

8 算法甲分析 时间复杂度O(NlogE)。 这种方法求出的位置，是绝对高度最小的位置。可以求相对高度最小的位置吗？ ——登高必自卑
我們對算法甲進行簡要分析。設E爲高度可能的範圍，二分答案的時間複雜度爲O(logE)，判斷每個答案合法的時間複雜度爲O(N)，因此總時間複雜度爲O(NlogE)。(click)不過我們僅僅求出了絕對高度最低點，也就是第二問“浮空島”的位置。但是對於第一問，求“瞭望塔”的位置，怎麼辦呢？

9 再次分析 猜想：瞭望塔一定建在山峰上。 反例：
我們猜想瞭望塔的位置和浮空島的位置有一定的關係。如果在山坡上看不到整個山脈，直觀感覺是向山峰上爬，於是容易想到的是瞭望塔一定被建在山峰上。(click)可是反例是存在的，例如下圖。

10 再次分析 猜想：瞭望塔一定在浮空岛周围的同一山峰的山坡上（距离不远）。 反例： 瞭望塔 浮空岛
觀察樣例我們發現，瞭望塔和浮空島似乎離得不遠，而且很可能在同一位置上。是不是瞭望塔一定在浮空島周圍的山坡上呢？(click)反例如下。

11 不識廬山眞面目 祇緣身在此山中 重新思考 一个山坡只能在山坡线的一侧被看到。 所有山坡可视区域的公共部分，就是整个山脉的可视区域。
接下来只需在可视区域内查找相对高度和绝对高度的最小的点了。 情況複雜，反例太多，看來並不是那麼容易考慮，只好換一個角度重新思考問題。前面說到，一個山坡只能在山坡所在直線的一側區域內被看到。(click)如果把所有山坡可視區域公共部份求出，那不就是整個山脈的可視區域了嗎？(click)接下來我們只需要在整個山脈的可視區域內找到縱座標最小的點和距離山脈折綫最近的點，就可以識別出“廬山真面目”了。 不識廬山眞面目 祇緣身在此山中

12 會當淩絕頂 一覽眾山小 算法乙 求所有半平面的交集。 可视区域就是“上方未封口的凸多边形”，抽象为分段函数。
——一覽眾山小 求所有半平面的交集。 可视区域就是“上方未封口的凸多边形”，抽象为分段函数。 扫描可视区域，求出相对高度和绝对高度最小的位置。 現在問題就是求所有山坡可視區域的交集了。具體地講，每個山坡的可視區域都是一個半平面。什麽是半平面？一條直線可以把平面分成兩部份，直線的一側就是一個半平面。整個山脈的可視區域就是這些半平面的交集。(click)根据半平面交的性质，整个山脉的可视区域就是一个上方不封口的凸多边形，在山脉横坐标范围内，可以認爲一个分段函数的圖像，每个部分都是一次函数。(click)此時就可以“一覽眾山小”了。 會當淩絕頂 一覽眾山小

13 算法乙 ——一覽眾山小 海平面 可视区域 如圖所示，所有可視區域的半平面交集與山脈一樣是一個分段的一次函數圖像。只需求出這個函數的最低點，以及兩個函數差的最小值即可。

14 算法乙分析 还可以改进吗？ 算法瓶颈：求半平面交。 时间复杂度：O(N^2)或O(NlogN)。 实现起来复杂。 ——一覽眾山小
該算法的瓶頸在於求所有半平面的交集，此後的函數作差和查找函數的最小值是線性的。已知的求半平面交的算法分別是O(N^2)和O(NlogN)，因此算法乙的時間複雜度是O(N^2)或O(NlogN)。(click)可惜的是，O(NlogN)求半平面交的算法實現起來較為複雜。这种算法还可以改进吗？

15 刪繁就簡三秋樹 領異標新二月花 算法丙 将直线按斜率排序，依次插入。 每次求交点，判断新插入的直线是否更优。 ——刪繁就簡三秋樹
我們發現，表示山坡可視區域的半平面，都是在直線的上方，也就是不等式y>=kx+b表示的平面區域。由於最終結果一定是下凸線的形式，我們就可以用一个堆棧來維護，只保留最優解。將所有直線按斜率從小到大排序，依次插入每一條直線。(click)每次判斷新插入直線與堆棧次頂直線交點，是否橫座標小於等於堆棧頂兩直線交點。如果是，則說明新的直線比當前棧頂直線更優，刪除棧頂直線再次判斷。 (click) 這樣我們“刪繁就簡”地維護，由於每條直線至多進入一次堆棧，所以維護的時間是線性的。 刪繁就簡三秋樹 領異標新二月花

16 算法丙 ——刪繁就簡三秋樹 p1 p2.x > p1.x p2
下面我們來演示一下。首先把所有的直線按照斜率從小到大排序，插入第一條直線。(click)插入第二條直線時，由於堆棧中只有一條，所以直接插入，兩直線交點是p1。(click)插入第三條直線以後，它與棧次頂直線交點是p2， (click)此時，p2的橫座標大於p1的橫座標，因此新插入直線不比棧頂直線優，直接插入即可。(click) p2.x > p1.x p2

17 算法丙 ——刪繁就簡三秋樹 p2.x <= p1.x p2 p1
繼續插入直線，與站次頂直線交于p2，它的橫座標比棧頂兩直線交點p1要小，因此它比棧頂直線優，刪除棧頂的直線。(click) p1

18 算法丙 ——刪繁就簡三秋樹 (click)此時已經處理完了所有的直線，堆棧中剩餘的直線，斜率依次遞減。(click)

19 算法丙 ——刪繁就簡三秋樹 海平面 可视区域 現在我們求出了可視區域的下凸線。(click)

20 恢恢乎 其於遊刃必有餘地矣 算法丙分析 时间复杂度：O(NlogN) 特殊问题用特殊方法解决。 ——刪繁就簡三秋樹
我們成功得用簡單的方法把求可視區域的時間複雜度優化到了O(N)，加上按斜率排序就是O(NlogN)，比一般的方法求半平面交簡單了不少。(click)由此可見，在不少時候，對於特定的問題採用特定的算法，比直接套用經典解法要更好。只有充分的理解問題的本質，才能做到“恢恢乎其於遊刃必有餘地矣”的境界。 恢恢乎 其於遊刃必有餘地矣

21 問渠那得清如許 爲有源頭活水來 总结 优化无止境，有O(N)的算法嗎？ 思考无止境，还有别的思路吗？ 学习无止境，还能学到别的知识吗？
——爲有源頭活水來 优化无止境，有O(N)的算法嗎？ 思考无止境，还有别的思路吗？ 学习无止境，还能学到别的知识吗？ 至此我們已經近乎完美地解決了這個問題，但是算法的優化是無止境的，事實上求下凸線還有線性的算法，請參見我的詳細題解。不過，與其掌握一道題的解法，不如通過這個題，學會思考的方法。思路的寬廣與否很大程度上取決於知識和經驗的積累。我們需要不斷地學習，思維才能像“有源活水”般永遠清澈。 問渠那得清如許 爲有源頭活水來

22 试题考查点 计算几何基本知识 二分思想 半平面交 单调性的应用 分段一次函数求最值

23 路曼曼其修遠兮 吾將上下而求索 感谢大家 郭家宝 byvoid1[at]gmail.com