QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726936 | #5649. Spinach Pizza | ohiostatescarlet | RE | 0ms | 0kb | Python3 | 1.7kb | 2024-11-09 10:31:29 | 2024-11-09 10:31:30 |
answer
import sys
import math
flush = sys.stdout.flush
class P:
def __init__(self, x, y):
self.x = x
self.y = y
def __repr__(self):
return f"({self.x}, {self.y})"
def __sub__(self, other):
return P(self.x - other.x, self.y - other.y)
def dist2(self):
return self.x * self.x + self.y * self.y
def dist(self):
return math.sqrt(self.dist2())
def __iter__(self):
return iter((self.x, self.y))
def triSemiPerim(a, b, c):
return (a + b + c) / 2
def triArea(a, b, c):
p = triSemiPerim(a, b, c)
return math.sqrt(p * (p - a) * (p - b) * (p - c))
def triPointsArea(a, b, c):
s1 = (b - a).dist()
s2 = (c - a).dist()
s3 = (c - b).dist()
return triArea(s1, s2, s3)
n = int(input())
p = [P(*map(int, input().split())) for _ in range(n)]
pointToIndex = {p[i]: i for i in range(n)}
turn = 0
if n % 2 == 1:
print("Beatrice")
turn = 1
else:
print("Alberto")
board = p.copy()
while len(board) > 2:
if turn == 0:
m = len(board)
best = float('inf')
bestIndex = 0
for i in range(m):
a = board[(i - 1) % m]
b = board[(i) % m]
c = board[(i + 1) % m]
area = triPointsArea(a, b, c)
if area < best:
best = area
bestIndex = i
print(pointToIndex[board[bestIndex]])
board.pop(bestIndex)
flush()
else:
# turn == 1
q = int(input())
board.remove(p[q])
# print(board)
turn = not turn
"""
4
0 0
6 1
5 3
1 4
"""
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
4 0 0 6 1 5 3 1 4 4
output:
Alberto 2