QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#893257#9804. Guess the Polygonucup-team134RE 0ms0kbPython32.0kb2025-02-10 16:56:572025-02-10 16:57:02

Judging History

This is the latest submission verdict.

  • [2025-02-10 16:57:02]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2025-02-10 16:56:57]
  • Submitted

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()
		
	

Details

Tip: Click on the bar to expand more detailed information

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

result: