1033 . Min/Max Enclosing Rectangle

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

A rectangle enclosing a set of points is valid if:

  1. all the points are inside the rectangle, or on the border of it.
  2. all edges of the rectangle are touched by some point of the given set. A point at a corner of the rectangle is considered touching its adjacent two edges, though.

Now given a set of points on the x-y plane, find their enclosing rectangle of minimum/maximum area respectively.

Input Format

Input contains multiple testcases, and is terminated by EOF.


In each of the testcases, an integer N (3<=n<=100000) describes the number of points. The following N lines each contain two integers describing the coordinate of the points. (0 <= |xi|,|yi| <= 107).


You can assume that there will be no testcase with all points collinear.

Output Format

For each testcase, output the answer in the following format:

Case #(case_id):

Minimum area = (min_enclosing_area)

Maximum area = (max_enclosing_area)

Print a blank line after each testcase.

Sample Input 1

3
-3 5
7 9
17 5
4
10 10
10 20
20 20
20 10

Sample Output 1

Case #1:
Minimum area = 80.000
Maximum area = 200.000

Case #2:
Minimum area = 100.000
Maximum area = 200.000

Hints

Info: 本題輸出為浮點數，絕對或相對誤差 1e-4 以下視為正確

Problem Source

Migrated from old NTUJ.

IMPROVED from ACM World Finals 2000, Problem D

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 200
Submit
Back to Top