QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#892196 | #9804. Guess the Polygon | ucup-team134# | RE | 112ms | 46044kb | Kotlin | 2.7kb | 2025-02-10 00:28:34 | 2025-02-10 00:28:39 |
Judging History
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