TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

66.7% (16/24)

Tags

Description

最近,王董買了一個海岸,IOICamp 2225 的總召巴乙己準備要借用這個海岸,來當作 IOICamp 2225 的其中一項活動──皮卡丘打排球大賽的活動場地。巴乙己為了好好觀賞這項 IOICamp 之中最精彩的活動,他建造了一座暸望塔,並且打算在皮卡丘打排球大賽期間待在暸望塔上。

這個海岸的海岸線可以被視為一條直線,而暸望塔正好被建造在海岸線上,皮卡丘打排球大賽的所有活動都在海岸線上進行,所以巴乙己只關心海岸線和海岸線的上空,於是他決定把海岸線和暸望塔所在的平面畫在二維平面上,海岸線是平面上從 (108×107,0)(108×107,0) 的線段(這個海岸線很長!),暸望塔頂端在這個平面上的座標是 (sx,sy)

在皮卡丘打排球大賽的前幾天,巴乙己發現海岸線上空出現了 N 朵烏雲,其中第 i 朵烏雲是在平面上的 (xi,1,yi)(xi,2,yi) 這條線段,烏雲會擋住巴乙己的視線,使他看不見一部份的海岸線。正式地說,巴乙己能看見海岸線上的一個點 (x,0),若 (sx,sy)(x,0) 這條線段不和任何烏雲相交(在端點也不行)。

為了確保良好的觀賽體驗,請告訴巴乙己,他不能看見的海岸線長度有多長。

Input Format

第一行有三個整數 N,sx,sy,代表海岸線上空出現了 N 朵烏雲,以及暸望塔頂端的座標是 (sx,sy)

接下來有 N 行,其中第 i 行包含三個整數 xi,1,xi,2,yi,代表第 i 朵烏雲對應到線段 (xi,1,yi)(xi,2,yi)

  • 1N5×105
  • 109sx109
  • 109xi,1<xi,2109
  • 0<yi<sy109

Output Format

輸出一個浮點數,代表巴乙己看不見的海岸線長度。若你的答案與正確答案的相對或絕對誤差 106,就會被視為正確。正式地說,假設正確答案是 a、你的答案是 b,你的答案會被視為正確的條件是 |ab|max(|a|,|b|,1)106

Sample Input 1

5 6 11
1 5 8
-7 -3 4
6 9 6
11 15 7
11 13 4

Sample Output 1

37.504761904761

Sample Input 2

5 6 11
-6 0 6
-2 4 6
6 12 6
10 16 6
8 11 6

Sample Output 2

44

Hints

目前的 IOICamp 沒有皮卡丘打排球大賽。

以下為兩筆範例測試資料的示意圖,綠色點是暸望塔頂端所在的位置、灰色陰影是巴乙己看不見的區域:

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~5 N=1 5
3 6~14 所有 yi 皆相同 30
4 2~25 無額外限制 65

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 2 4
3 1000 262144 65536 2 4
4 1000 262144 65536 2 4
5 1000 262144 65536 2 4
6 1000 262144 65536 3 4
7 1000 262144 65536 3 4
8 1000 262144 65536 3 4
9 1000 262144 65536 3 4
10 1000 262144 65536 3 4
11 1000 262144 65536 3 4
12 1000 262144 65536 3 4
13 1000 262144 65536 3 4
14 1000 262144 65536 3 4
15 1000 262144 65536 4
16 1000 262144 65536 4
17 1000 262144 65536 4
18 1000 262144 65536 4
19 1000 262144 65536 4
20 1000 262144 65536 4
21 1000 262144 65536 4
22 1000 262144 65536 4
23 1000 262144 65536 4
24 1000 262144 65536 4
25 1000 262144 65536 4