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
|
|
Mihai Negrean:
2013-04-15 17:26:28
I have a question: the problem states that "You can arbitrary rotate this polygon."
|
Added by: | Pavel Kuznetsov |
Date: | 2007-03-25 |
Time limit: | 1s |
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 guile SCM qobi ST WHITESPACE |
Resource: | Vologda 2007 |