시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB87787.500%

문제

stonejjun은 최근에 폭발적으로 유행하는 성벽 디펜스 게임을 시작했다. 이 게임은 성벽을 넓히고, 성벽에 함정, 대포, 문 등을 적절히 배치해서 몰려오는 적을 막는 게임이다.

영토에 기둥을 몇 개 세우면 자동으로 성벽이 지어진다. 구체적으로, 성벽의 모양은 둘레 또는 내부에 모든 기둥을 포함하는 가장 작은 볼록 다각형이다. 같은 좌표에 여러 기둥이 있을 수도 있다.

게임을 처음 시작할 때, (-1,-1), (-1,1), (1,-1), (1,1)의 4개의 위치에 기둥이 설치되어있다. 하지만, stonejjun은 지갑전사이기 때문에 바로 N개의 기둥을 추가로 설치하였다. 

그럼에도 불구하고 계속해서 패배를 한 stonejjun은 화가 나서 현금으로 30도, 60도, 90도, 120도, 150도 확장권을 구매하였다. 각도 확장권은 이 게임만의 특별한 시스템이다. 현재 stonejjun이 x개의 기둥을 가지고 있다고 하자. 이 상태에서 a도 확장권을 사용하면 다음 과정을 거쳐 기둥과 성벽이 다시 지어진다.

  1. 위치가 다른 모든 기둥의 쌍 (I, J)에 대해, 각 IPJa도이면서 선분 IPPJ의 길이가 같은 모든 점 P에 새로운 기둥을 설치한다.
  2. 기존에 있었던 기둥과 새로운 기둥을 사용하여 성벽을 다시 짓는다.

성벽의 길이는 곧 국력! stonejjun은 자신이 가진 확장권을 적절한 순서로 사용하여 성벽의 길이를 최대로 하려고 한다. 현재 기둥의 위치와 가지고 있는 확장권의 개수가 주어질 때, stonejjun이 만들 수 있는 새로운 성벽의 최대 길이를 출력하시오. 

입력

첫째 줄에는 추가로 설치할 기둥의 개수 N이 주어진다. 

둘째 줄부터 N개의 줄에 걸쳐 추가로 설치하는 기둥 중 i번째 기둥의 x좌표 xi와 y좌표 yi가 공백으로 구분되어 주어진다.

마지막 줄에는 30도 확장권, 60도 확장권, 90도 확장권, 120도 확장권, 150도 확장권 각각의 개수 A, B, C, D, E가 순서대로 주어진다. 

출력

stonejjun이 만들 수 있는 새로운 성벽의 최대 길이를 출력한다. 절대/상대 오차는 10-6까지 허용한다.

제한

  • 1 ≤ N ≤ 100,000
  • -10,000 ≤ xi, yi ≤ 10,000이고, 모든 좌표는 정수이다.
  • 0 ≤ A,B,C,D,E ≤ 5

예제 입력 1

1
0 0
0 1 0 0 0

예제 출력 1

16.000000

출처

Contest > Semi-Game Cup > Semi-Game Cup 2 H번