1、Clouds解題浙江紹興柯橋中學(xué) 黃勁松問(wèn)題簡(jiǎn)述天空中有 n 朵云，在風(fēng)吹之下以恒定速度 v=(vx ,vy ) 向同一個(gè)方向持續(xù)移動(dòng)，也就是說(shuō)，當(dāng)時(shí)間為 t（t0）時(shí)，云上初始坐標(biāo)為(x, y)的點(diǎn)移到坐標(biāo)為( x + t*vx,y + t*vy )的位置。為簡(jiǎn)單起見(jiàn)，假設(shè)云是多邊形的（而且其頂點(diǎn)具有整數(shù)坐標(biāo)）。多邊形不一定是凸的，但是每個(gè)多邊形的任意兩條邊不相交（允許具有公共的端點(diǎn)）。云和云可能會(huì)。地面上有一人造之上，有一顆人造控制中心，位于坐標(biāo)(0,0)處，在控制中心正上方的云層。一道激光束從控制中心筆直地向上射向人造，這道激光束用于與進(jìn)行通信。然而，當(dāng)激光束的光路被云遮住時(shí)，通信就會(huì)中

2、斷。最初激光束不與任何一片云相交。在觀測(cè)期間，會(huì)有若干個(gè)這樣的時(shí)段，在這些時(shí)段期間激光束的光路穿過(guò)一片或幾片云，使得通信中斷。甚至當(dāng)激光束遇到云的某個(gè)頂點(diǎn)時(shí)，通信也會(huì)有瞬間的中斷。你需要寫(xiě)一個(gè)程序來(lái)計(jì)算在所有云移過(guò)之前，通信會(huì)中斷多少次。54321-3-2-112345678-1數(shù)據(jù)范圍1云的數(shù)目 n10003云的邊數(shù) k1000產(chǎn)生的交點(diǎn)數(shù)目 v100000-109每個(gè)點(diǎn)的坐標(biāo) xi,yi 109-109云的移動(dòng)速度 vx,vy 109算法分析運(yùn)用逆向思維可以知道，云的移動(dòng)可以看作激光的反方向移動(dòng)。于是問(wèn)題轉(zhuǎn)化成了激光從原點(diǎn)位置開(kāi)始朝某個(gè)方向移動(dòng)的時(shí)候一共穿云多少次。53423211-3-2

3、-112345678-1Figure 1如圖 1 所示，激光的移動(dòng)路線（圖中虛線所示）與云相交出了若干條線段，如果是單個(gè)的點(diǎn)，則可以看作是長(zhǎng)度為0 的線段（如多邊形2 與虛線的一個(gè)交點(diǎn)）；兩條靠在一起的線段可以看作合并在一起的一條線段（如虛線與多邊形 3、4 交成的線段可以合并為一條線段）那么問(wèn)題所要求的就是這些線段的總數(shù)目。首先，要找出虛線與多邊形相交所成的所有交點(diǎn)。在例圖中可以看到，虛線與多邊形相交得到了 7 個(gè)交點(diǎn)。如果把多邊形 2 的那個(gè)與虛線相交的頂點(diǎn)拆作兩個(gè)點(diǎn)的話（以下稱(chēng)為某個(gè)點(diǎn)一次），對(duì)于上圖的情況，可以簡(jiǎn)交點(diǎn)按照與原點(diǎn)距離排序之后兩兩配對(duì)，得到所有的線段，再對(duì)靠在一起的線段進(jìn)行

4、合并就可以得到問(wèn)題的。4但是虛線與多邊形相交的情況并不只有例圖中所示的那么幾種。虛線與多邊形的交有可能出現(xiàn)如下的一些特殊情況：ABCDEFFigure 2在最左邊的一種情況中，如果上半部分是多邊形A的話，需要一次，而如果下半部分是多邊形的話，需要B 一次。這個(gè)細(xì)節(jié)實(shí)在太難考慮清楚，需要換個(gè)角度思考。于是來(lái)對(duì)交點(diǎn)進(jìn)行分類(lèi)：普通的交點(diǎn)看作 0 類(lèi)點(diǎn)，上圖點(diǎn) E 也可以看作 0 類(lèi)點(diǎn)；A 看作 1 類(lèi)點(diǎn)； B，C，D 看作 2 類(lèi)點(diǎn)； F 看作 3 類(lèi)點(diǎn)。之所以把 B 看作和 C，D 同類(lèi)是因?yàn)?A 是線段的左端點(diǎn)，而在接下來(lái)的操作中，對(duì)端點(diǎn)進(jìn)行逐個(gè)判斷的時(shí)候，會(huì)先到A，這里需要通過(guò)A 來(lái)一些信息。

5、通過(guò)如上的歸類(lèi)之后，虛線與多邊形的交點(diǎn)都可以歸在 4 種類(lèi)型當(dāng)中。按照交點(diǎn)到原點(diǎn)由近到遠(yuǎn)的順序來(lái)逐個(gè)每個(gè)點(diǎn)，從而模擬激光穿云的過(guò)程。在過(guò)程中，如下信息：當(dāng)前激光是否在多邊形i 的，用incloudi表示，初始都是false；當(dāng)前激光是否在多邊形i 的某條邊上，用 on_edgei表示，初始都是 false；當(dāng)前激光一共穿過(guò)了多少層云，用clod 表示，初始是 0；當(dāng)前激光一共穿過(guò)了多少條邊，用edge 表示，初始是 0；當(dāng)clod 和edge 都為 0，且當(dāng)前到的點(diǎn)與上一個(gè)點(diǎn)不是相同頂點(diǎn)的話（有些時(shí)候不同的邊與虛線交在同一個(gè)點(diǎn)上，的時(shí)候就產(chǎn)生了重復(fù)的點(diǎn)），那么當(dāng)前激光穿過(guò)一塊空白處，通信正常，

6、此時(shí)把穿云的次數(shù)加 1；否則激光就正被云擋著，通信斷路。對(duì)于當(dāng)前到的點(diǎn)，假設(shè)它是云 k 上的一個(gè)點(diǎn)：如果它屬于 0 類(lèi)點(diǎn)或者是2 類(lèi)點(diǎn)，那么改變 incloudk的值，如果 incloudk變?yōu)閒alse 了，那么 clod 的值減 1，否則clod 的值加 1；如果它屬于 1 類(lèi)點(diǎn)或者 2 類(lèi)點(diǎn)，那么改變on_edgek的值，如果on_edgek變?yōu)閒alse 了，那么edge 的值減 1，否則edge 的值加 1；如果它屬于 3 類(lèi)點(diǎn)，不需要做任何操作。來(lái)對(duì)這一系列的操作做一下解釋?zhuān)喝绻す馀龅搅?0 類(lèi)點(diǎn)或 2 類(lèi)點(diǎn)的時(shí)候，它肯定會(huì)進(jìn)入或者走出一塊云的區(qū)域，所以需要修改incloud 的

7、值；如果激光碰到了 1 類(lèi)點(diǎn)或者 2 類(lèi)點(diǎn)，那么說(shuō)明它即將進(jìn)入或者走出一條邊的區(qū)域，同理改變 on_edge 的值。這里為什么需要同時(shí)兩個(gè)值clod 和edge 呢？是否可以忽略掉edge？我們以Figure 2 中的第二種情況為例來(lái)說(shuō)明edge 的用處：如果C，D 的下半部分是云，在到點(diǎn)C 時(shí)，需要改變當(dāng)前激光穿過(guò)的云的數(shù)目；而當(dāng)C，D 上半部分是云，在種復(fù)雜情況的點(diǎn)C 時(shí)，不需要改變當(dāng)前激光穿過(guò)的云的數(shù)目。為了避免這，故而用到了edge。分析一下這個(gè)算法的復(fù)雜度：找出所有的交點(diǎn) O(nk)對(duì)于所有的交點(diǎn)進(jìn)行一次排序 O(vlogv)統(tǒng)計(jì)激光穿云的次數(shù) O(v)總時(shí)間復(fù)雜度為 O(nk+vl

8、ogv)具體實(shí)現(xiàn)在實(shí)現(xiàn)的過(guò)程中，用叉積來(lái)判斷線段與虛線是否相交，同時(shí)計(jì)算交點(diǎn)的位置。需要注意的是，由于數(shù)據(jù)范圍比較大，有時(shí)候不同交點(diǎn)之間的距離是如此的小以至于無(wú)法用系統(tǒng)提供的實(shí)數(shù)類(lèi)型來(lái)進(jìn)行判斷。為了解決這個(gè)問(wèn)題，必須用兩個(gè) 64 位整數(shù)表示的分?jǐn)?shù)形式來(lái)個(gè) 64 位整數(shù)的乘積。設(shè)激光移動(dòng)方向的向量為(vx,vy)，與之相交的線段的兩個(gè)端點(diǎn)為(ax,ay)， (bx,by)。則交點(diǎn)離原點(diǎn)的位置可表示為： (ax*by-bx*ay)/(vy*(ax-bx)-vx*(ay-by)來(lái)解釋一下這個(gè)公式：，(ax*by-bx*ay)代表了向量 A 與向量 B 的叉積；(vy*(ax-bx)-vx*(ay-by)代表了向量 C 與向量 D 的叉積。E 代表的是原點(diǎn)到交點(diǎn)的那條向量。因?yàn)橛衸AB|=|CE|（可以根據(jù)向量叉乘的幾何意義來(lái)證明，具體證明略），所以|AB|/|CD|=|E|/|D|。上述公式所表示意義就是交點(diǎn)到原點(diǎn)的帶符號(hào)距離與|D|的比值。而