KPPOLY - Projections Of A Polygon


You are given a convex polygon on Cartesian coordinate system. It has projections on X and Y-axis. You can arbitrary rotate this polygon. What minimum and maximum sum of projections can you achieve?

Input

First line contains one integer number N (3 ≤ N ≤ 100) - number of polygon's vertices. Following N lines contain vertex coordinates Xi and Yi. All numbers are integers. Vertices are given in clockwise or anticlockwise direction. No two vertices coincide. No three consecutive vertices lie on the same line. All coordinates do not exceed 10000 by absolute value.

Output

Write minimum and maximum value of sum of the polygon's projections. Separate them by a space. Your answer should not differ with the correct one more than 10-6.

Example

Input:
4
0 0
0 1
1 1
1 0

Output:
2 2.828427124

hide comments
Akshay Aradhya: 2018-03-29 14:07:15

what does "minimum and maximum sum of projections" mean ?

lu: 2017-03-01 16:09:57

O(n) solution

weathervane: 2017-01-22 20:46:15

The problem statement is unclear, as can be seen from its age, its one vote, and the few people who have attempted it. The single test case reveals nothing by providing a square. Please, at least provide two small but interesting examples. Unfortunately in this scheme, you cannot downvote a question until you have solved it.

mkmostafa: 2015-08-25 00:04:53

first go AC!! :D

npsabari: 2013-06-20 01:51:55

Precision matters a lot! Be careful about that

Branfili: 2013-04-19 11:54:44

@Mihai
I believe it's right from every perspective.

Last edit: 2013-04-23 18:33:58
Mihai Negrean: 2013-04-15 17:26:28

I have a question: the problem states that "You can arbitrary rotate this polygon."

This rotation is done with respect to what point? The center of mass of the polygon? The center of the Cartesian system? Any point that belongs to the polygon?


Added by:Pavel Kuznetsov
Date:2007-03-25
Time limit:0.134s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi SCM guile ST WHITESPACE
Resource:Vologda 2007