回分類題庫
h044: B.下雨天
關鍵字: NPSC 2008 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 72 Times / 62 Users | Submit : 200 Times / 67 Users | Accepted rate : 93%
題目加入時間 : 2011-11-10 10:43

Content: 简体中文

有些人很討厭下雨,不過總是存在著靠著下雨賺錢的人。

小雨是一個靠賣遮雨棚賺錢的生意人,他總是有各式各樣款式的遮雨棚要賣。不過,為了說服顧客,他總是吹噓他的遮雨棚可以擋住最多的雨。

小陽正準備向小雨買遮雨棚,不過他也不想花太多錢在遮雨棚上,在各式各樣的遮雨棚中,他想挑選最划算的遮雨棚來買。遮雨棚是用空間上的兩個點(x1, y1),(x2, y2)連成的線段以及他的單位價格s 來表示,遮雨棚的價格是以它的長度乘以單位價格來決定,而能夠擋住雨的量是以遮雨棚在x 軸上的投影長度決定,小陽認為最划算的遮雨棚是讓價格除以擋住雨的量愈小愈好。

在小雨天花亂墜的推銷中,小陽完全對怎麼買遮雨棚沒有頭緒,轉而向你求救,聰明的你能幫他解決這個問題嗎?

Input:

第一行有一個整數代表之後有幾組測資。
每一組測資開頭以一個正整數 n (0 < n <= 100) 代表小雨有幾種遮雨棚要賣。之後 n 行每行會有五個整數x1, y1, x2, y2, s (0 <= x1, y1, x2, y2 <= 50, 0 < s <= 10, x1 與 x2 不相等),分別表示每個遮雨棚。

Output:

對每組測資輸出一行,輸出第幾個遮雨棚是最划算的,遮雨棚是從1 開始算。可以假設沒有兩個遮雨棚一樣划算。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
1
2
2 1 6 0 2
1 3 4 5 10

Sample Output :

1

Hint :

Author :

NPSC 2008 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum