QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795934 | #9804. Guess the Polygon | ucup-team1134# | TL | 0ms | 0kb | Python3 | 2.9kb | 2024-12-01 04:46:18 | 2024-12-01 04:46:19 |
Judging History
answer
from fractions import Fraction
from collections import defaultdict
def gcd(a, b):
while b:
a, b = b, a % b
return a
class Rational:
def __init__(self, x=0, y=1):
if y < 0:
x = -x
y = -y
g = gcd(abs(x), abs(y))
self.x = x // g
self.y = y // g
def __add__(self, other):
z = self.y * other.y // gcd(self.y, other.y)
nx = z // self.y * self.x + z // other.y * other.x
ny = z
return Rational(nx, ny)
def __sub__(self, other):
z = self.y * other.y // gcd(self.y, other.y)
nx = z // self.y * self.x - z // other.y * other.x
ny = z
return Rational(nx, ny)
def __mul__(self, other):
nx = self.x * other.x
ny = self.y * other.y
if ny < 0:
nx = -nx
ny = -ny
return Rational(nx, ny)
def __truediv__(self, other):
nx = self.x * other.y
ny = self.y * other.x
if ny < 0:
nx = -nx
ny = -ny
return Rational(nx, ny)
def __lt__(self, other):
return self.x * other.y < self.y * other.x
def __eq__(self, other):
return self.x * other.y == self.y * other.x
def __str__(self):
return f"{self.x}/{self.y}" if self.y != 1 else f"{self.x}"
def main():
import sys
input = sys.stdin.read
data = input().splitlines()
Q = int(data[0])
idx = 1
results = []
for _ in range(Q):
N = int(data[idx])
idx += 1
S = []
use = []
for i in range(N):
a, b = map(int, data[idx].split())
idx += 1
S.append((a, b))
use.append(a)
S.sort()
use = sorted(set(use))
X = []
l = 0
for i in range(len(use)):
r = l
while r < N and S[r][0] == use[i]:
r += 1
if i == 0 or i == len(use) - 1:
if r - l > 1:
print(f"? {use[i]} {1}")
sys.stdout.flush()
a, b = map(int, input().split())
X.append(Rational(a, b))
else:
X.append(Rational(0, 1))
else:
print(f"? {use[i]} {1}")
sys.stdout.flush()
a, b = map(int, input().split())
X.append(Rational(a, b))
l = r
ans = Rational(0, 1)
for i in range(len(use) - 1):
su = X[i] + X[i + 1]
su = su * Rational(use[i + 1] - use[i], 1)
ans = ans + su
ans = ans * Rational(1, 2)
print(f"! {ans.x} {ans.y}")
sys.stdout.flush()
if __name__ == "__main__":
main()
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
2 4 3 0 1 3 1 1 0 0