結果

問題 No.2180 Comprehensive Line Segments
ユーザー Shirotsume
提出日時 2022-09-28 14:30:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,787 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 418,048 KB
最終ジャッジ日時 2024-11-17 00:50:21
合計ジャッジ時間 94,183 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other AC * 4 WA * 7 RE * 1 TLE * 13
権限があれば一括ダウンロードができます

ソースコード

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
n = ii()
XY = [li() for _ in range(n)]
if n == 1:
    print(1)
    exit()
lines = set()

for i in range(n):
    x1, y1 = XY[i]
    for j in range(n):
        x2, y2 = XY[j]
        if x1 == x2:
            lines.add((x1, INF))
        else:
            a = (y2-y1) / (x2-x1)
            b = y1 - a * x1
            lines.add((a, b))

S = set()
for x1, y1 in lines:
    for x2, y2 in lines:
        if x1 == x2:
            continue
        if y1 == INF:
            S.add((x1, x2 * x1 + y2))
        elif y2 < INF:
            S.add(((y2 - y1) / (x2 - x1), (x1 * y2 - x2 * y1) / (x2 - x1)))
S = list(S)
m = len(S)
mask = [[0] * m for _ in range(m)] 
for i in range(m):
    x1, y1 = S[i]
    for j in range(m):
        x2, y2 = S[j]
        mm = 0
        if i == j:
            for k in range(n):
                x,y= XY[k]
                if x == x1 and y == y1:
                    mm |= 1 << k
        elif x1 == x2:
            for k in range(n):
                x, y = XY[k]
                if x == x1:
                    mm |= 1 << k
        else:
            a = (y2-y1)/(x2-x1)
            b = y2-a*x2
            for k in range(n):
                x, y = XY[k]
                if a*x+b == y:
                    mm |= 1<<k
        mask[i][j] = mm
dp = [[INF] * m for _ in range(1<<n)]

for i in range(m):
    dp[0][i] = 0

for bit in range(1<<n):
    for fr in range(m):
        for to in range(m):
                dp[bit | mask[fr][to]][to] = min(dp[bit | mask[fr][to]][to], dp[bit][fr] + 1)


ans = n
for bit in range(1<<n):
    ans = min(ans, n - bin(bit).count('1') + min(dp[bit]))
    
print(ans)
0