QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795156 | #9804. Guess the Polygon | ucup-team3734# | RE | 150ms | 58048kb | Java11 | 4.1kb | 2024-11-30 18:08:41 | 2024-11-30 18:08:42 |
Judging History
answer
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
static Scanner scanner = new Scanner(System.in);
private static Fraction ask(Fraction x) {
System.out.println("? " + x.getNumerator() + " " + x.getDenominator());
System.out.flush();
int p = scanner.nextInt();
int q = scanner.nextInt();
return new Fraction(p, q);
}
private static void solve() {
int n = scanner.nextInt();
List<Fraction[]> points = new ArrayList<>();
for (int i = 0; i < n; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
points.add(new Fraction[]{new Fraction(x, 1), new Fraction(y, 1)});
}
Collections.sort(points, (a, b) -> a[0].compareTo(b[0]));
List<Fraction> answers = new ArrayList<>(Collections.nCopies(n, new Fraction(0, 1)));
for (int i = 1; i < n - 1; i++) {
answers.set(i, ask(points.get(i)[0]));
}
Fraction S = new Fraction(0, 1);
for (int i = 0; i < n - 1; i++) {
Fraction width = points.get(i + 1)[0].subtract(points.get(i)[0]);
Fraction height = answers.get(i).add(answers.get(i + 1));
S = S.add(width.multiply(height));
}
S = S.divide(BigInteger.valueOf(2));
System.out.println("! " + S.getNumerator() + " " + S.getDenominator());
System.out.flush();
}
public static void main(String[] args) {
int t = scanner.nextInt();
for (int i = 0; i < t; i++) {
solve();
}
}
}
class Fraction implements Comparable<Fraction> {
private BigInteger numerator;
private BigInteger denominator;
public Fraction(int numerator, int denominator) {
this.numerator = BigInteger.valueOf(numerator);
this.denominator = BigInteger.valueOf(denominator);
simplify();
}
public Fraction(BigInteger numerator, BigInteger denominator) {
this.numerator = numerator;
this.denominator = denominator;
simplify();
}
public Fraction add(Fraction other) {
BigInteger newNumerator = this.numerator.multiply(other.denominator)
.add(other.numerator.multiply(this.denominator));
BigInteger newDenominator = this.denominator.multiply(other.denominator);
return new Fraction(newNumerator, newDenominator);
}
public Fraction subtract(Fraction other) {
BigInteger newNumerator = this.numerator.multiply(other.denominator)
.subtract(other.numerator.multiply(this.denominator));
BigInteger newDenominator = this.denominator.multiply(other.denominator);
return new Fraction(newNumerator, newDenominator);
}
public Fraction multiply(Fraction other) {
BigInteger newNumerator = this.numerator.multiply(other.numerator);
BigInteger newDenominator = this.denominator.multiply(other.denominator);
return new Fraction(newNumerator, newDenominator);
}
public Fraction divide(BigInteger divisor) {
return new Fraction(this.numerator, this.denominator.multiply(divisor));
}
private void simplify() {
BigInteger gcd = numerator.gcd(denominator);
numerator = numerator.divide(gcd);
denominator = denominator.divide(gcd);
if (denominator.compareTo(BigInteger.ZERO) < 0) {
numerator = numerator.negate();
denominator = denominator.negate();
}
}
@Override
public int compareTo(Fraction other) {
BigInteger left = this.numerator.multiply(other.denominator);
BigInteger right = other.numerator.multiply(this.denominator);
return left.compareTo(right);
}
@Override
public String toString() {
return numerator + "/" + denominator;
}
public BigInteger getNumerator() {
return numerator;
}
public BigInteger getDenominator() {
return denominator;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 150ms
memory: 58048kb
input:
2 4 3 0 1 3 1 1 0 0 2 1 2 1 3 0 0 999 1000 1000 999 1999 1000
output:
? 1 1 ? 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 3 1
output:
? 1 1 ? 1 1 ! 9 2