解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 F - No challenge No life

contents

  1. 1. Problem
  2. 2. Solution

Problem

這次要挑戰的題目為 UVa 12647 - Balloon，由於網路上有一些線段樹的作法，如

http://www.cnblogs.com/yours1103/p/3426212.html

這裡可以看到有一些人利用線段樹來完成操作，實際上的做法根據掃描線，y 座標從高度低到高、或者是高到低的線段依序放入，到時候查找第一個獲最後一個覆蓋的線段編號。

UVa 12647 - Balloon 主要是在問，給予一些天花板，請問放置一個氣球，氣球會沿著天花板歪斜的地方移動 (如果沒歪則停止)，詢問最後停留的位置。有可能會飛到無窮遠，則輸出最後的 x 座標，反之輸出停留的 (x, y) 地點。如果發生一個地點有數個天花板，發生擦邊情況，則氣球會依據第一個碰觸到的天花板進行移動。

Solution

既然發現它們 (搜尋可以找到至少兩個大大的線段樹寫法) 基本上都是按照覆蓋的方式，找到覆蓋編號去完成移動、建造飛行的所有可能。

明顯地，由於天花板線段的斜率有正有負，不能保證根據 y 座標排序可以決定飛行到下一個的高度的 x 範圍。因此交錯 y 座標線段，讓覆蓋方案失效。

下面有數組測資，可以讓史蒂芙掉測資、也會讓網址中的代碼掉。史蒂芙認為覆蓋不好，那用最大最小值去維護如何！這樣也許就好點了吧？但不幸地，這麼做一樣會遇到排序 y 的問題，不管怎麼排序，都會造成建構方法不正確。

challenge 的題目還不太會傳，中間有點小問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h> 
int main() {
//	puts("4 1");
//	puts("3 1 12 4");
//	puts("5 2 2 3");
//	puts("1 4 4 3");
//	puts("7 5 14 5");
//	puts("4");
    puts("3 3");
    puts("5 5 10 4");
    puts("2 2 6 4");
    puts("0 3 4 4");
    puts("0");
    puts("1");
    puts("2");
//	puts("7 4");
//	puts("3 1 12 4");
//	puts("5 2 2 3");
//	puts("1 4 4 3");
//	puts("7 5 14 5");
//	puts("25 5 30 4");
//	puts("22 2 26 4");
//	puts("20 3 24 4");
//	puts("4");
//	puts("20");
//	puts("21");
//	puts("22");
    return 0;
}
/*
3 3
5 5 10 4
2 2 6 4
0 3 4 4
0
1 
2
4 1
3 1 12 4
5 2 2 3
1 4 4 4
7 5 14 5
4
4 1
3 1 12 4
5 2 2 3
1 4 4 3
7 5 14 5
4
*/