結果

問題 No.2180 Comprehensive Line Segments
コンテスト
ユーザー Shirotsume
提出日時 2022-10-11 17:08:52
言語 PyPy3
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,212 bytes
コンパイル時間 322 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 1,553,260 KB
最終ジャッジ日時 2024-11-17 01:04:12
合計ジャッジ時間 85,534 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1 MLE * 1
other AC * 9 TLE * 6 MLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
mod = 998244353
from collections import deque
from fractions import Fraction as frac
class Point:
    def __init__(self, x: frac, y: frac):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return (self.x == other.x and self.y == other.y)

    def __hash__(self):
        return hash((self.x, self.y))

    def __lt__(self, other):
        if(self.x == other.x):
            return (self.y < other.y)
        return (self.x < other.x)

    def show(self):
        print(self.x, self.y)

    def calcLine(self, other):
        x1 = self.x;  y1 = self.y
        x2 = other.x;  y2 = other.y
        if(x1 == x2):
            return Line(frac(1), frac(0), x1)
        a = (y1 - y2) / (x1 - x2)
        c = y1 - a * x1
        return Line(-a, frac(1), c)

class Line:
    def __init__(self, a: frac, b:frac, c:frac):
        self.a = a
        self.b = b
        self.c = c

    def __eq__(self, other):
        return (self.a == other.a and self.b == other.b and self.c == other.c)

    def __hash__(self):
        return hash((self.a, self.b, self.c))

    def show(self):
        print((self.a, self.b, self.c))

    def intersection(self, other) -> Point:
        p = self.a * other.b - other.a * self.b
        if(p == frac(0)):
            return None
        q = other.b * self.c - self.b * other.c
        x = q / p
        y = (other.c - other.a * x) / other.b if(self.b == 0) else (self.c - self.a * x) / self.b
        return Point(x, y)

n = ii()
P = [Point(*map(frac, input().split())) for _ in range(n)]

if n == 1:
    exit(print(1))
lcnt = 0
L = []
for i in range(n):
    for j in range(i + 1, n):
        l = P[i].calcLine(P[j])
        L.append(l)

for l1 in L:
    for l2 in L:
        if l1 == l2:
            continue
        p = l1.intersection(l2)
        if(p is None or p in P):
            continue
        P.append(p)

dir_lis = [[None] * len(P) for _ in range(len(P))]

for i in range(len(P)):
    for j in range(i + 1, len(P)):
        l = P[i].calcLine(P[j])
        if l not in L:
            continue
        dir_lis[i][j] = (L.index(l), P[i] < P[j])
        dir_lis[j][i] = (L.index(l), P[i] > P[j])


dp = [[[[inf]*2 for _ in [0]*(len(L) + 1)] for _ in [0]*len(P)] for _ in [0]*(1 << n)]
q = deque()
for i in range(n):
    q.append((0, 1 << i, i, len(L), 0))
    dp[1 << i][i][len(L)][0] = 0
goal = (1 << n) - 1
ans = inf
cnt = 0
while q:
    c, b, v, l, a = q.popleft()
    if(l != len(L) and c > dp[b][v][l][a]):
        continue
    if(b == goal):
        ans = c
        break
    for nv in range(len(P)):
        nb = b
        if(nv < n):
            nb = b | (1 << nv)
        if(dir_lis[v][nv] is None):
            continue
        nl, na = dir_lis[v][nv]
        nowc = c
        if(l == len(L) or (L[l], a) != (L[nl], na)):
            nowc += 1
        if(nowc >= dp[nb][nv][nl][na]):
            continue
        dp[nb][nv][nl][na] = nowc
        if(nowc == c):
            q.appendleft((nowc, nb, nv, nl, na))
        else:
            q.append((nowc, nb, nv, nl, na))
print(ans)
0