結果

問題 No.2180 Comprehensive Line Segments
コンテスト
ユーザー Shirotsume
提出日時 2022-10-02 00:46:44
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,962 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 81,748 KB
実行使用メモリ 734,308 KB
最終ジャッジ日時 2024-11-17 00:56:40
合計ジャッジ時間 111,850 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 MLE * 1
other AC * 2 WA * 7 TLE * 13 MLE * 3
権限があれば一括ダウンロードができます

ソースコード

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 fractions import Fraction as frac

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 __str__(self):
        return str((self.a, self.b, self.c))

    
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 __str__(self):
        return str((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 = frac((y1 - y2), (x1 - x2))
        c = y1 - a * x1
        return Line(-a, frac(1), 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)
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


n = ii()
XY = [li() for _ in range(n)]
if n == 1:
    print(1)
    exit()
lines = set()
p = Point(1, 2)
for i in range(n):
    x1, y1 = XY[i]
    p1 = Point(x1, y1)
    for j in range(n):
        x2, y2 = XY[j]
        p2 = Point(x2, y2)
        lines.add(p1.calcLine(p2))
S = set()

for l1 in lines:
    for l2 in lines:
        if intersection(l1, l2) is not None:
            S.add(intersection(l1, l2))
        
S = list(S)
m = len(S)

mask = [[0] * m for _ in range(m)] 
for i in range(m):
    p1 = S[i]
    for j in range(m):
        p2 = S[j]
        mm = 0
        if i == j:
            for k in range(n):
                pn = Point(*XY[k])
                if p1 == pn:
                    mm |= 1<<k

        else:
            l = p1.calcLine(p2)
            for k in range(n):
                p3 = Point(*XY[k])
                if p3.x * l.a + p3.y * l.b + l.c == 0:
                    mm |= 1<<k
        mask[i][j] = mm
from collections import Counter, defaultdict, deque
dp = [[defaultdict(lambda: inf) for _ in range(m)] for _ in range(1<<n)]
for i in range(m):
    dp[0][i][-inf] = 0
q = deque()
for i in range(m):
    q.append((0, i, -inf))
while q:
    bit, fr, di = q.popleft()
    if bit == (1<<n)-1:
        break
    for to in range(m):
        if bit | mask[fr][to] == bit and dp[bit|mask[fr][to]][to]:
            continue
        p1 = S[fr]
        p2 = S[to]
        l = p1.calcLine(p2)
        now = frac(l.a, l.b) if l.b != 0 else inf
        for v in list(dp[bit][fr].keys()):
            if v == now and (not(dp[bit | mask[fr][to]][to]) or max(dp[bit | mask[fr][to]][to]) == inf):
                dp[bit | mask[fr][to]][to][now] = min(dp[bit | mask[fr][to]][to][now], dp[bit][fr][v])
                q.appendleft((bit|mask[fr][to], to, now))
            elif v != now and (not(dp[bit | mask[fr][to]][to]) or max(dp[bit | mask[fr][to]][to]) == inf):
                dp[bit | mask[fr][to]][to][now] = min(dp[bit | mask[fr][to]][to][now], dp[bit][fr][v] + 1)
                q.append((bit|mask[fr][to], to, now))
ans = n - 1

for i in range(m):
    for v in dp[-1 + (1<<n)][i].values():
        ans = min(ans, v)
print(ans)
0