← 返回题目列表

AtCoder · typical90_i

009. 三点角度(★6)

中文机器翻译题面 查看原题

配点: 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