루미 알고리즘

#1361다이아Kohagen

PO 2015 훈련 캠프코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Oskar håller på att bygga en kohage. Till sin hjälp har han n staketstolpar utspridda i en cirkel. Han vill välja fyra av dessa stolpar att bygga ett staket med.

För att minimera kostnaden för det stycke land han då måste köpa vill han inte att hagen blir större än den behöver vara. Han har räknat fram att korna måste ha minst m kvadratmeters utrymme att gå runt och äta gräs på. Vad är arean av den minsta hagen Oskar kan bygga, givet minimi-kravet?

Indata

En rad med tre heltal, n, m och r, som beskriver antalet stolpar, kravet för arean och cirkelns radie. Det gäller att 1 ≤ m ≤ 1000000000 och 1 ≤ r ≤ 1000. Sedan följer en rad med n flyttal a_1, a_2, ..., a_n där a_i anger vinkeln vid vilken stolpe i befinner sig angivet i grader. Det gäller att 0 ≤ a_i < 360.

Utdata

Skriv ut ett flyttal - den minsta möjliga arean av en kohage som uppfyller Oskars krav. Om det inte finns en hage som uppfyller kraven, skriv ut -1. Svaret anses rätt om det absoluta eller relativa felet är mindre än 10^-11 (så se till att skriva ut med mer precision än så).

Poängsättning

GruppPoängvärdeGränser
1234 ≤ n ≤ 50
2214 ≤ n ≤ 200 Stolparna bildar en regelbunden n-hörning
3344 ≤ n ≤ 200 Den minsta hagen som uppfyller kraven är den största möjliga hagen.
4134 ≤ n ≤ 200
594 ≤ n ≤ 400

예제

예제 1

입력
5 1 1
0 45 90 180 270
출력
1.207106781186547

예제 2

입력
8 2 3
270 0 180 45 90 135 225 305
출력
5.258870794958175

예제 3

입력
6 3 1
2.43253 27.88574 76.65430 13.53719 165.94723 112.00374
출력
-1

출처 표기

출처: Programmeringsolympiaden 2015년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.