QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795263#9804. Guess the Polygonucup-team2112#RE 16ms11740kbPython31.5kb2024-11-30 19:04:012024-11-30 19:04:01

Judging History

This is the latest submission verdict.

  • [2024-11-30 19:04:01]
  • Judged
  • Verdict: RE
  • Time: 16ms
  • Memory: 11740kb
  • [2024-11-30 19:04:01]
  • Submitted

answer

from fractions import Fraction
import sys

T = int(input())

while T > 0:
    T -= 1
    n = int(input())
    point = []
    for i in range(n):
        x, y = map(int, input().split())
        point.append([x, y])
    point.sort(key=lambda item: item[0])
    pre = Fraction(0)
    pre_x = point[0][0]
    res = Fraction(0)


    i = 1
    while i < n:
        x, y = point[i]
        if i == n - 1:
            p, q = 0, 1
            res += (Fraction(p, q) + pre) * (x - pre_x)
            break
        j = i
        while j < n and point[j][0] == x:
            j += 1
        cnt = j - i
        # print(f'index = {i}, {j}')
        if cnt == 1:
            print(f"? {x} {1}")
            sys.stdout.flush()
            p, q = map(int, input().split())
            res += (Fraction(p, q) + pre) * (x - pre_x)
            pre = Fraction(p, q)
            pre_x = x
        else:
            cur = Fraction(x + pre_x, 2)
            print(f"? {cur.numerator} {cur.denominator}")
            sys.stdout.flush()
            p, q = map(int, input().split())
            res += (Fraction(p, q) + pre) * (Fraction(x + pre_x, 2) - pre_x)
            res += (3 * Fraction(p, q) - pre) * (x - Fraction(x + pre_x, 2))
            print(f"? {x} {1}")
            sys.stdout.flush()
            p, q = map(int, input().split())
            pre = Fraction(p, q)
            pre_x = x

        i = j
    res /= 2
    print(f"! {res.numerator} {res.denominator}")
    sys.stdout.flush()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 16ms
memory: 11740kb

input:

2
4
3 0
1 3
1 1
0 0
1 1
2 1
3
0 0
999 1000
1000 999
1999 1000

output:

? 1 2
? 1 1
! 3 1
? 999 1
! 1999 2

result:

ok correct! (2 test cases)

Test #2:

score: -100
Dangerous Syscalls

input:

9
4
1 1
1 3
3 0
0 0
3 2
3 1

output:

? 1 2
? 1 1
! 9 2

result: