Problem:

Problem C: Satake likes straight

Problem

	

Satake君は曲がったことが嫌いです。

例えば、鉛筆や箸、家が曲がった形をしているのは嫌いですし、右折や左折などの行動をとることも嫌いです。

さて、XY 平面上で暮らすSatake君は $N$ 個のお店 $(X_{1},Y_{1}),(X_{2},Y_{2}), \ldots , (X_{N},Y_{N})$ で買い物をするようお使いを頼まれました。座標 $(0, 0)$ にある家から $(1, 0)$ の方向を向いた状態で出発し、すべてのお店で買い物をしたあと、家に帰ります。お店を回る順番は自由です。Satake君はお使いとして次に示す任意の行動を何度でも行うことができます。

	
向いている方向に好きなだけ進む

	
お店か家と同じ座標のとき時計回りか反時計回りに好きな角度だけその場で回転する

	
お店と同じ座標のとき座標や向いている方向の状態を維持したまま買い物をする

先程も言ったようにSatake君は曲がることが嫌いです。心の準備ができるように、Satake君が行動2.で回転する角度の和の最小値を求めてください。例として、時計回りに $90^{\circ}$ 回転した後、反時計回りに $90^{\circ}$ 回転した場合、角度の和は $180^{\circ}$ となります。

Input

入力は以下の形式で与えられます。

$N$
$X_{1}$ $Y_{1}$
$\vdots$
$X_{N}$ $Y_{N}$

入力は $N+1$ 行からなります。

$1$ 行目には買い物をする店の個数を表す $N$ が与えられます。

$2$ 行目から続く $N$ 行には、買い物をするお店の座標 $X_{i}, Y_{i}$ が空白区切りで与えられます。

Constraints

入力は以下の条件を満たします。

	
$2 \le N \le 8$

	
$-1000 \le X_{i}, Y_{i} \le 1000  \quad (1 \le i \le N)$

	
$(X_{i}, Y_{i}) \ne (0, 0)        \quad (1 \le i \le N)$

	
$(X_{i}, Y_{i}) \ne (X_{j}, Y_{j}) \quad (i \ne j)$

	
入力はすべて整数

Output

Satake君が回転する角度の和の最小値を度数法で出力してください。ただし想定解との絶対誤差が $10^{-4}$ 以下のときのみ正解とします。

Sample Input 1

2
0 1
0 -1

Sample Output 1

450.00000000

Satake君は最初 $(1, 0)$ 方向を向いて出発することに注意してください。

Sample Input 2

3
1 0
0 1
-2 -1

Sample Output 2

386.565051



Sample input:
2
0 1
0 -1


Sample output:
450.00000000

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    from itertools import permutations
    def dot(a,b):
        return sum(list(map(lambda x : x[0]*x[1], zip(a,b))))

    n = I()
    p = LIR(n)
    ans = float("inf")
    for l in permutations(range(n),n):
        x,y = [0,0]
        m = 0
        v = [1,0]
        for i in l:
            s,t = p[i]
            nv = [s-x,t-y]
            m += math.acos(dot(v,nv)/(dot(v,v)*dot(nv,nv))**0.5)
            x,y = s,t
            v = [nv[0],nv[1]]
        s,t = 0,0
        nv = [s-x,t-y]
        m += math.acos(dot(v,nv)/(dot(v,v)*dot(nv,nv))**0.5)
        ans = min(ans, m)
    print(ans*180/math.pi)
    return


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from math import atan2, degrees
from itertools import permutations

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
px = py = 0
ans = float("inf")
for t in permutations(XY):
    a = 0
    deg = 0
    for x, y in t + ([0, 0],):
        d = degrees(atan2(y-py, x-px))
        delta = deg - d
        if delta < 0: delta += 360
        if delta > 180: delta = 360 - delta
        a += delta

        px, py = x, y
        deg = d
    ans = min(a, ans)
print(ans)