結果

問題 No.2180 Comprehensive Line Segments
コンテスト
ユーザー Shirotsume
提出日時 2022-09-28 15:03:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,304 bytes
コンパイル時間 484 ms
コンパイル使用メモリ 82,824 KB
実行使用メモリ 581,768 KB
最終ジャッジ日時 2024-11-17 00:53:18
合計ジャッジ時間 97,820 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1 TLE * 1
other AC * 5 WA * 6 TLE * 13 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
INF = 1000000
mod = 998244353
n = ii()
XY = [li() for _ in range(n)]
if n <= 2:
    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 = round((y2-y1) / (x2-x1) * 100) / 100
            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 == y2 == INF:
            continue
        if y1 == INF:
            S.add((x1, round((x2 * x1 + y2) * 100 ) / 100))
        elif y2 == INF:
            S.add((x2, round((x1 * x2 + y1) * 100) / 100))
        elif y1 < INF and y2 < INF:
            S.add((round((y2 - y1) / (x2 - x1) * 100) / 100, round((x1 * y2 - x2 * y1) / (x2 - x1) * 100) / 100))
S = list(S)
m = len(S)
eps = 10 ** (-5)
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 abs(x - x1) <= eps:
                    mm |= 1 << k
        elif x1 == x2:
            for k in range(n):
                x, y = XY[k]
                if abs(x - x1) <= eps:
                    mm |= 1 << k
        else:
            a = (y2-y1)/(x2-x1)
            b = y2-a*x2
            for k in range(n):
                x, y = XY[k]
                if abs(a*x+b - y) <= eps:
                    mm |= 1<<k
        mask[i][j] = mask[j][i] = mm
ans = n - 1
for i in range(m):
    for j in range(m):
        for k in range(m):
            if mask[i][j] == (1 << n) - 1:
                print(1)
                exit()
            if mask[i][j] | mask[j][k] == (1 << n) - 1:
                ans = 2
dp = [[INF] * m for _ in range(1<<n)]

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

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)
            
if not dp[(1<<n)-1]:
    print(1)
    exit()
print(min([ans] + dp[(1<<n)-1]))
0