009 - Three Point Angle（★6）
Editorial
/ 
/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点: 6 点
問題文
座標平面上に相異なる N 個の点 P_1, \dots, P_N があり、点 P_i の座標は (X_i, Y_i) です。
この N 個の点から相異なる3点 P_i, P_j, P_k を選び、\angle P_i P_j P_k を最大にしたいです。この最大値を度数法で出力してください。
ただし、0^\circ \leq \angle P_i P_j P_k \leq 180^{\circ} とします。
\angle P_i P_j P_kとは
点 P_i \to 点 P_j \to 点 P_k の折れ線で構成される角の大きさのことです。
制約
- 3 \leq N \leq 2000
- 0 \leq X_i, Y_i \leq 10^9 (1 \leq i \leq N)
- (X_i, Y_i) \neq (X_j, Y_j) (1 \leq i < j \leq N)
- 入力される値は全て整数である
入力
入力は以下の形式で標準入力から与えられます。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
\angle P_i P_j P_k の最大値を度数法で出力してください。 ただし、相対誤差または絶対誤差が 10^{-7} 以下であれば正解として扱われます。
入力例 1
3 0 0 0 10 10 10
出力例 1
90
P_1, P_2, P_3 の座標はそれぞれ (0, 0), (0, 10), (10, 10) です。
- \angle P_1 P_2 P_3=90^\circ
- \angle P_2 P_3 P_1=45^\circ
- \angle P_3 P_1 P_2=45^\circ
であり、 \angle P_1 P_2 P_3=90^\circ が最大なので、90 と出力すればよいです。
入力例 2
5 8 6 9 1 2 0 1 0 0 1
出力例 2
171.869897645844
\angle P_2 P_3 P_4 = 171.869\cdots^\circ が最大です。
入力例 3
10 0 0 1 7 2 6 2 8 3 5 5 5 6 7 7 1 7 9 8 8
出力例 3
180
\angle P_1 P_6 P_{10}=180^\circ が最大です。
入力例 4
40 298750376 229032640 602876667 944779015 909539868 533609371 231368330 445484152 408704870 850216874 349286798 30417810 807260002 554049450 40706045 380488344 749325840 801881841 459457853 66691229 5235900 8100458 46697277 997429858 827651689 790051948 981897272 271364774 536232393 997361572 449659237 602191750 294800444 346669663 792837293 277667068 997282249 468293808 444906878 702693341 894286137 845317003 27053625 926547765 739689211 447395911 902031510 326127348 582956343 842918193 235655766 844300842 438389323 406413067 862896425 464876303 68833418 76340212 911399808 745744264 551223563 854507876 196296968 52144186 431165823 275217640 424495332 847375861 337078801 83054466 648322745 694789156 301518763 319851750 432518459 772897937 630628124 581390864 313132255 350770227
出力例 4
179.9834340684232