QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795934#9804. Guess the Polygonucup-team1134#TL 0ms0kbPython32.9kb2024-12-01 04:46:182024-12-01 04:46:19

Judging History

This is the latest submission verdict.

  • [2024-12-01 04:46:19]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-12-01 04:46:18]
  • Submitted

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

output:


result: