f636: 老農夫的三個兒子
Tags :
Accepted rate : 4人/9人 ( 44% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-25 11:06

Content

老農夫有一塊矩形的農地(W*H),老農夫過世後把土地留給了三個兒子,但三個兒子長久失和,因此決定將農地均分為三塊,各自獨立。

農地北邊有一石牆A,南邊有一石牆B,石牆上已存在一些樁點,因此三個兒子決定從A石牆上選兩個點(a1, a2),

B石牆上選兩個點(b1, b2),建立兩道圍欄 (a1,b1) 及 (a2, b2),如此希望能將土地分成三等份,

但如何選擇AB石牆上的樁點,似乎有些困難,請幫忙解決此一難題。

(其中 a1 < a2b1 < b2)

 

   (圖例為範例測資1)

 

Input
第一行四個整數 n, m, W, H,
(2<= n,m <=100,000,  W,H <= 1000,000,000)
其中 n 代表A石牆上的點數,m 代表B石牆上的點數,
第二行有 n 個整數,代表A石牆上各點的 x 座標(左側為 0)。
第三行有 m 個整數,代表B石牆上各點的 x 座標(左側為 0)。
Output
一行輸出 (a1, b1) - (a2, b2)
如範例。
如有多筆符合的結果,請輸出 (a1, a2) 最小數字序者。
如不可能等分,則輸出 impossible
 
Sample Input #1
5 4 6 5
1 2 3 4 5
1 2 3 4
Sample Output #1
(1,3)-(4,4)
Sample Input #2
8 5 12 10
3 4 1 5 6 2 7 8
2 4 11 8 6
Sample Output #2
(2,6)-(5,11)
Sample Input #3
4 3 6 5
1 3 4 5
2 4 5 
Sample Output #3
impossible
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (7%): 1.0s , <1K
公開 測資點#1 (7%): 1.0s , <1K
公開 測資點#2 (7%): 1.0s , <1M
公開 測資點#3 (7%): 1.0s , <1M
公開 測資點#4 (8%): 1.0s , <1M
公開 測資點#5 (8%): 1.0s , <1M
公開 測資點#6 (8%): 1.0s , <1M
公開 測資點#7 (8%): 1.0s , <1M
公開 測資點#8 (8%): 1.0s , <1M
公開 測資點#9 (8%): 1.0s , <1M
公開 測資點#10 (8%): 1.0s , <10M
公開 測資點#11 (8%): 1.0s , <50M
公開 測資點#12 (8%): 1.0s , <50M
Hint :
Tags:
出處:
林口高中練習題 [管理者:
hshua (hshua)
]


ID User Problem Subject Hit Post Date
25943
becaido (Caido)
f636
對#11疑問
42 2021-07-06 17:14
24288
asnewchien@g... (david)
f636
241 2021-02-04 13:43