QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#892196#9804. Guess the Polygonucup-team134#RE 112ms46044kbKotlin2.7kb2025-02-10 00:28:342025-02-10 00:28:39

Judging History

This is the latest submission verdict.

  • [2025-02-10 00:28:39]
  • Judged
  • Verdict: RE
  • Time: 112ms
  • Memory: 46044kb
  • [2025-02-10 00:28:34]
  • Submitted

answer

import java.math.BigInteger
import java.util.*

data class Fraction(val numerator: BigInteger, val denominator: BigInteger) {
    init {
        require(denominator != BigInteger.ZERO) { "Denominator cannot be zero" }
    }

    operator fun plus(other: Fraction): Fraction {
        val newNumerator = numerator * other.denominator + other.numerator * denominator
        val newDenominator = denominator * other.denominator
        return Fraction(newNumerator, newDenominator).reduce()
    }

    operator fun times(value: Int): Fraction {
        return Fraction(numerator * value.toBigInteger(), denominator).reduce()
    }

    operator fun div(value: Int): Fraction {
        return Fraction(numerator, denominator * value.toBigInteger()).reduce()
    }

    private fun gcd(a: BigInteger, b: BigInteger): BigInteger {
        return if (b == BigInteger.ZERO) a else gcd(b, a % b)
    }

    private fun reduce(): Fraction {
        val gcdValue = gcd(numerator.abs(), denominator.abs())
        return Fraction(numerator / gcdValue, denominator / gcdValue)
    }

    override fun toString(): String {
        return "$numerator/$denominator"
    }
}

fun qr(k: Int): Fraction {
    println("? $k 1")
    System.out.flush()
    val (x, y) = readln().split(" ").map { it.toBigInteger() }
    return Fraction(x, y)
}

fun trap(a: Fraction, b: Fraction, d: Int): Fraction {
    return (a + b) * d / 2
}

fun main() {
    val t = readln().toInt()
    repeat(t) {
        val n = readln().toInt()
        val pts = mutableListOf<Pair<Int, Int>>()
        
        repeat(n) {
            val (x, y) = readln().split(" ").map { it.toInt() }
            pts.add(x to y)
        }

        pts.sortBy { it.first }

        if (pts.first().first == pts.last().first) {
            println("! 0 1")
            System.out.flush()
            return@repeat
        }

        var lst = Fraction(BigInteger.ZERO, BigInteger.ONE)

        if (pts[0].first != pts[1].first) {
            lst = Fraction(BigInteger.ZERO, BigInteger.ONE)
        } else {
            lst = qr(pts[0].first)
        }

        var area = Fraction(BigInteger.ZERO, BigInteger.ONE)

        for (i in 0 until n - 2) {
            if (pts[i].first != pts[i + 1].first) {
                val d = pts[i + 1].first - pts[i].first
                val novi = qr(pts[i + 1].first)
                area += trap(lst, novi, d)
                lst = novi
            }
        }

        if (pts[n - 2].first != pts[n - 1].first) {
            area += trap(lst, Fraction(BigInteger.ZERO, BigInteger.ONE), pts[n - 1].first - pts[n - 2].first)
        }

        println("! ${area.numerator} ${area.denominator}")
        System.out.flush()
    }
}

详细

Test #1:

score: 100
Accepted
time: 112ms
memory: 46044kb

input:

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

output:

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

result:

ok correct! (2 test cases)

Test #2:

score: -100
Runtime Error

input:

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

output:

? 1 1
! 9 2

result: