b591: 最小容量造船問題
Tags : 二元一次方程式
Accepted rate : 20人/24人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-10-21 13:29

Content

如果我要要造一艘船,我們要考慮的不只是它的容量 y 還要考慮它的重量 x,如果 x, y 必須滿足 n 個條件式 y >= aix+bi ,i = 1,2, ....,n。現在你是造船廠的工程師,你想造出一艘滿足條件且容量 y 最小的船,寫一個程式來計算吧。

例如有一艘船要滿足兩個條件式 y >= x+3 及 y >= -x+5,則最小的 y 值應該是 4 ,而對應的 x 應該是 1。但是你必須注意 x 不能小於 0 ,因此如果只有一個條件式 y >= x+5,則最小的 y 值應該是 5 ,而對應的 x 應該是 0。

Input

每一組測試資料有兩行,第一行數字 n 代表有多少條件式,第二行有 2n 個數字,每兩個數字 a, b 代表一個條件式 y >= ax+b,1<=n<=2000,-100 <= a,b <= 100 但不包括 0

遇到輸入 n 值為 0 時結束

 

Output

對於每組測試資料輸出兩個浮點數 y 和 x,輸出的精確度到小數後三位,如果 y 值小於等於 0,就只需要輸出一個 0 當答案

Sample Input
1
1 5
1
2 -1
1
1 -4
2
1 3 -1 5
2
3 3 -2 5
2
2 3 -1 5
0
Sample Output
5.000 0.000
0
0
4.000 1.000
4.200 0.400
4.333 0.667
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 5.0s , <1M
Hint :
Tags:
二元一次方程式
出處:
SEARCC-ISSC國際學生程式設計競賽 [管理者:
spocktsai (囧rz)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」