結果

問題 No.2180 Comprehensive Line Segments
ユーザー ShirotsumeShirotsume
提出日時 2022-09-28 14:30:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,787 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 348,140 KB
最終ジャッジ日時 2024-04-28 10:31:59
合計ジャッジ時間 6,964 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 104 ms
76,676 KB
testcase_01 AC 54 ms
64,852 KB
testcase_02 AC 39 ms
53,244 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

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