22853번 - 기둥과 성벽 디펜스 게임 스페셜 저지

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

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

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

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

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

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

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

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

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

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

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