QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#893257 | #9804. Guess the Polygon | ucup-team134 | RE | 0ms | 0kb | Python3 | 2.0kb | 2025-02-10 16:56:57 | 2025-02-10 16:57:02 |
Judging History
answer
from fractions import Fraction
import sys
import math
def qr(k):
print(f"? {k.numerator} {k.denominator}")
sys.stdout.flush()
x,y=map(int,input().split())
return Fraction(x,y)
def trap(a,b,d):
return d*(a+b)/2
t = int(input())
for k in range(t):
n=int(input())
pts=[]
for i in range(n):
x,y=map(int,input().split())
pts.append((x,y))
pts.sort()
if pts[0][0] == pts[-1][0]:
print("! 0 1")
sys.stdout.flush()
continue
last=-1
cnt=0
xs=[]
for i in range(0,n):
if pts[i][0]==last:
cnt=cnt+1
else:
if cnt != 0:
xs.append((last,cnt))
last=pts[i][0]
cnt=1
xs.append((last,cnt))
vals=[]
if xs[0][1]==1:
vals.append((Fraction(xs[0][0],1),0))
else:
X=Fraction(xs[0][0],1)+Fraction(1,3)
vals.append((X,qr(X)))
for i in range(1,len(xs)-1):
if xs[i][1]==1:
X=Fraction(xs[i][0],1)
vals.append((X,qr(X)))
else:
X=Fraction(xs[i][0],1)+Fraction(1,3)
vals.append((X,qr(X)))
X=X-Fraction(2,3)
vals.append((X,qr(X)))
if xs[-1][1]==1:
vals.append((Fraction(xs[-1][0],1),0))
else:
X=Fraction(xs[-1][0],1)-Fraction(1,3)
vals.append((X,qr(X)))
left = []
right = []
ind=0
left.append(0)
for i in range(1,len(xs)):
while ind < len(vals) - 1 and vals[ind+1][0] <= xs[i][0]:
ind = ind+1
if vals[ind][0] == xs[i][0]:
left.append(vals[ind][1])
else:
a=vals[ind][1]
b=vals[ind-1][1]
d1=xs[i][0]-vals[ind][0]
d2=vals[ind][0]-vals[ind-1][0]
my = a+(a-b)*d1/d2
left.append(my)
ind=0
for i in range(0,len(xs)-1):
while ind < len(vals) - 1 and vals[ind+1][0] < xs[i][0]:
ind = ind+1
if vals[ind+1][0] == xs[i][0]:
right.append(vals[ind+1][1])
else:
a=vals[ind+1][1]
b=vals[ind+2][1]
d1=vals[ind+1][0]-xs[i][0]
d2=vals[ind+2][0]-vals[ind+1][0]
my = a+(a-b)*d1/d2
right.append(my)
right.append(0)
area=Fraction(0,1)
for i in range(0,len(left)-1):
d=xs[i+1][0]-xs[i][0]
area=area+d*(right[i]+left[i+1])/2
print(f"! {area.numerator} {area.denominator}")
sys.stdout.flush()
詳細信息
Test #1:
score: 0
Runtime Error
input:
2 4 3 0 1 3 1 1 0 0 5 3 4 3
output:
? 4 3 ? 2 3 ! 2 1