3215 -- Median of Lines

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Language:

Median of Lines

Time Limit: 6000MS		Memory Limit: 131072K
Total Submissions: 1504		Accepted: 311

Description

In the Cartesian plane, there are n (odd) distinct lines f_i(x) = a_i + xb_i (i = 1, 2, …, n). For each x, F(x) denotes the median of {f₁(x), f₂(x), ..., f_n(x)}. You are required to find the solution space of the equation F(x) = 0.

Input

The input contains multiple test cases. Each test case have n + 1 lines the first one of which contains n (1 < n < 10⁵ and odd). Then n lines follow, each of which contains two integers a_i and b_i (|a_i| ≤ 10⁸, 0 ≤ b_i < 10⁸). A zero follows the last test case.

Output

For each test case, output the solution space as an interval on a separate line. Interval boundaries should be rounded to two digits beyond the decimal point. “+inf” and “-inf” are used to represent positive and negative infinities. The solution space will form at most one interval in this problem. If the solution space is empty, just output “-1”.

Sample Input

Sample Output

(-inf,0.00]
[-1.00,-0.50]
-1
[-0.50,-0.50]
(-inf,+inf)

Hint

Be cautious about outputting “-0.00”.

Illustration of the second test case in the sample input:

Source

POJ Monthly--2007.04.01, dearboy

[Submit] [Go Back] [Status] [Discuss]

Home Page Go Back To top