結果

問題 No.2180 Comprehensive Line Segments
コンテスト
ユーザー Shirotsume
提出日時 2022-10-07 15:42:35
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,252 bytes
コンパイル時間 457 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 1,044,064 KB
最終ジャッジ日時 2024-11-17 00:58:21
合計ジャッジ時間 100,029 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 3
other AC * 2 WA * 5 TLE * 11 MLE * 7
権限があれば一括ダウンロードができます

ソースコード

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(1, 0, x1)
        a = (y1 - y2)/(x1 - x2)
        c = y1 - a * x1
        return Line(-a, 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()
ans = n - 1
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:
    a, b, c = l1.a, l1.b, l1.c
    flag = True
    for i in range(n):
        x, y = XY[i]
        if a * x + b * y + c != 0:
            flag = False
    if flag:
        print(1)
        exit()
    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:
        print(dp[bit][fr][di])
        exit()
    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 = (l.a / l.b) if l.b != 0 else inf
        for v in list(dp[bit][fr].keys()):
            if abs(v - now) <= 10 ** (-6):
                if dp[bit | mask[fr][to]][to][now] > dp[bit][fr][v]:
                    dp[bit | mask[fr][to]][to][now] = dp[bit][fr][v]
                    q.appendleft((bit|mask[fr][to], to, now))
            else:
                if dp[bit | mask[fr][to]][to][now] > dp[bit][fr][v] + 1:
                    dp[bit | mask[fr][to]][to][now] = dp[bit][fr][v] + 1
                    if bit|mask[fr][to]==2**n-1:
                        q.append((bit|mask[fr][to], to, now))
                    else:
                        q.append((bit|mask[fr][to], to, now))
                    
for i in range(m):
    for v in dp[-1 + (1<<n)][i].values():
        ans = min(ans, v)
print(ans)
0