結果

問題 No.2180 Comprehensive Line Segments
ユーザー MasKoaTS
提出日時 2022-10-11 21:04:43
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,624 bytes
コンパイル時間 479 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 189,996 KB
最終ジャッジ日時 2024-11-17 01:01:00
合計ジャッジ時間 108,988 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other AC * 9 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import permutations
from fractions import Fraction as frac
input = sys.stdin.readline


class Vector2:
	def __init__(self, x: frac, y: frac):
		self.x = x
		self.y = y

	def __sub__(self, other):
		return Vector2(other.x - self.x, other.y - self.y)

def be_same_inclination(one: Vector2, other: Vector2) -> bool:
	if(one.x == 0):
		return (other.x == 0 and one.y / other.y > 0)
	a = other.x / one.x
	return (a * one.y == other.y and a > 0)

def calc_outer_product(one: Vector2, other: Vector2) -> frac:
	return one.x * other.y - one.y * other.x


def sgn(x: frac) -> int:
	if(x > 0):
		return 1
	if(x < 0):
		return -1
	return 0

def is_continuous_bit(bit: int) -> bool:
	while(bit):
		if((bit & 3) == 3):
			return True
		bit >>= 1
	return False


"""
Main Code
"""

N = int(input())
P = [Vector2(*map(frac, input().split())) for _ in [0] * N]

if(N == 1):
	print(1)
	exit(0)

ans = N
for p in permutations(P):
	lis = [p[1] - p[0]]
	flag = False
	for i in range(1, N - 1):
		v = p[i + 1] - p[i]
		if(be_same_inclination(lis[-1], v)):
			continue
		if(calc_outer_product(lis[-1], v) == 0):
			flag = True
			break
		lis.append(v)
	if(flag):
		continue

	M = len(lis)
	if(M <= 2):
		ans = min(ans, M)
		continue

	for i in range(1 << (M - 2)):
		if(is_continuous_bit(i)):
			continue
		bit = i << 1
		cnt = M
		for j in range(1, N - 1):
			if(((bit >> j) & 1) == 0):
				continue
			v1, v2, v3 = lis[j-1:j+2]
			op1, op2, op3 = calc_outer_product(v1, v2), calc_outer_product(v2, v3), calc_outer_product(v1, v3)
			if(sgn(op1) == sgn(op2) == sgn(op3)):
				cnt -= 1
		ans = min(ans, cnt)

print(ans)
0