Just Look Up

시간 제한1초메모리 제한2048 MB

요약
지구를 원점으로 한 별들의 좌표가 주어질 때, 내부에 별이 하나도 들어가지 않는 원뿔의 최대 반각을 구하고, 반공간이 가능하면 90도를 출력한다.
난이도

어려움10점 중 8점

유형
기하, 정렬, 수학, 이분 탐색
정답자
아직 제출이 없습니다

문제

The year is 2432, and after millennia of looking at the sky, astronomers have found all the stars. This arduous journey, which started with the discovery of the Sun in 450 BC, has finally come to an end. Since scientists can never be content, they have turned to the next best thing, and decided to find planets instead.

A passionate group, the Planet Discovery Aficionados (PDA), has already started working on it! To find new planets, they have built the Large Astronomical Telescope of Amazing Might (LATAM) – a telescope that is extremely sensitive to light and thus can see even the tiniest planets.

When pointed to the sky, LATAM’s field of view encompasses the portion of space enclosed strictly by a circular cone, with the vertex located at the Earth and extending infinitely away from it. The angle of the cone corresponding to the viewing area of LATAM can be adjusted by the members of PDA, and it ranges from 0∘0^\circ when the cone collapses to a line, to 90∘90^\circ when it encompasses a full half-space.

Sadly, because LATAM is so sensitive to light, if there are any stars in its field of view the picture will be a bright mess, and PDA won’t be able to see any planets. They ask for your help to determine the largest possible viewing angle that does not include any stars. PDA has enough money to travel anywhere on Earth, so you are allowed to point LATAM in any direction in the sky.

Because the universe is sufficiently large, PDA considers that all the stars and the Earth are fixed 3D points, with the Earth located at (0,0,0)(0, 0, 0). The group will give you the coordinates of all the stars in the universe. They hope that with this information, you will be able to complete your task.

입력

The first line contains an integer NN (1≤N≤5001 ≤ N ≤ 500) indicating the number of stars in the universe.

Each of the next NN lines describes a star with three integers XX, YY and ZZ (−103≤X,Y,Z≤103−10^3 ≤ X, Y, Z ≤ 10^3), representing that the star is located at (X,Y,Z)(X, Y, Z). No two stars share the same location, and no star is located at (0,0,0)(0, 0, 0).

출력

Output a single line with the largest possible angle the telescope can be set to without observing any stars. If there exists a direction where a full half-space contains no stars, report 90∘90^\circ. The output must have an absolute or relative error of at most 10−410^{−4}.

예제2

  1. 예제 1

    입력
    6
    1 0 0
    -1 0 0
    0 1 0
    0 -1 0
    0 0 1
    0 0 -1
    
    예상 출력
    54.7356103172
    
  2. 예제 2

    입력
    2
    314 314 314
    1 1 1
    
    예상 출력
    90