QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#893311#9804. Guess the Polygonucup-team134WA 0ms3584kbC++175.2kb2025-02-10 17:13:052025-02-10 17:13:06

Judging History

This is the latest submission verdict.

  • [2025-02-10 17:13:06]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3584kb
  • [2025-02-10 17:13:05]
  • Submitted

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

__int128 gcd(__int128 a, __int128 b){
	if(a==0)return b;
	if(b==0)return a;
	if(a==1)return b;
	return gcd(b%a,a);
}
struct Fraction {
    __int128 num, den;
    Fraction(__int128 n = 0, __int128 d = 1) {
        __int128 g = gcd(n, d);
        num = n / g;
        den = d / g;
        if (den < 0) {
            num = -num;
            den = -den;
        }
    }
    Fraction operator+(const Fraction &other) const {
        return Fraction(num * other.den + other.num * den, den * other.den);
    }
    Fraction operator-(const Fraction &other) const {
        return Fraction(num * other.den - other.num * den, den * other.den);
    }
    Fraction operator*(const Fraction &other) const {
        return Fraction(num * other.num, den * other.den);
    }
    Fraction operator/(const Fraction &other) const {
        return Fraction(num * other.den, den * other.num);
    }
    bool operator<=(const Fraction &other) const {
        return num * other.den <= other.num * den;
    }
    bool operator<(const Fraction &other) const {
        return num * other.den < other.num * den;
    }
    bool operator==(const Fraction &other) const {
        return num == other.num && den == other.den;
    }
};

Fraction qr(const Fraction &k) {
    cout << "? " << (long long)k.num << " " << (long long)k.den << endl;
    fflush(stdout);
    long long x, y;
    cin >> x >> y;
    return Fraction(x, y);
}

Fraction trap(Fraction a, Fraction b, Fraction d) {
    return d * (a + b) / Fraction(2, 1);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<pair<int, int>> pts(n);
        for (int i = 0; i < n; i++) {
            cin >> pts[i].first >> pts[i].second;
        }
        sort(pts.begin(), pts.end());

        if (pts[0].first == pts[n - 1].first) {
            cout << "! 0 1" << endl;
            fflush(stdout);
            continue;
        }

        vector<pair<int, int>> xs;
        int last = -1, cnt = 0;
        for (auto &p : pts) {
            if (p.first == last) {
                cnt++;
            } else {
                if (cnt > 0) xs.push_back({last, cnt});
                last = p.first;
                cnt = 1;
            }
        }
        xs.push_back({last, cnt});

        vector<pair<Fraction, Fraction>> vals;
        if (xs[0].second == 1) {
            vals.push_back({Fraction(xs[0].first, 1), Fraction(0, 1)});
        } else {
            Fraction X = Fraction(xs[0].first, 1);
            X = X + Fraction(1, 3);
            vals.push_back({X, qr(X)});
        }

        for (size_t i = 1; i < xs.size() - 1; i++) {
            if (xs[i].second == 1) {
                Fraction X(xs[i].first, 1);
                vals.push_back({X, qr(X)});
            } else {
                Fraction X(xs[i].first, 1);
                X = X - Fraction(1, 3);
                vals.push_back({X, qr(X)});
                X = X + Fraction(2, 3);
                vals.push_back({X, qr(X)});
            }
        }
        if (xs.back().second == 1) {
            vals.push_back({Fraction(xs.back().first, 1), Fraction(0, 1)});
        } else {
            Fraction X(xs.back().first, 1);
            X = X - Fraction(1, 3);
            vals.push_back({X, qr(X)});
        }

        vector<Fraction> left(xs.size()), right(xs.size());
        int ind = 0;
        left[0] = Fraction(0, 1);
        for (size_t i = 1; i < xs.size(); i++) {
            while (ind < (int)vals.size() - 1 && vals[ind + 1].first <= Fraction(xs[i].first, 1)) {
                ind++;
            }
            if (vals[ind].first == Fraction(xs[i].first, 1)) {
                left[i] = vals[ind].second;
            } else {
                Fraction a = vals[ind].second, b = vals[ind - 1].second;
                Fraction d1 = Fraction(xs[i].first, 1) - vals[ind].first;
                Fraction d2 = vals[ind].first - vals[ind - 1].first;
                left[i] = a + (a - b) * d1 / d2;
            }
        }

        ind = -1;
        for (size_t i = 0; i < xs.size() - 1; i++) {
            while (ind < (int)vals.size() - 1 && vals[ind + 1].first < Fraction(xs[i].first, 1)) {
                ind++;
            }
            if (vals[ind + 1].first == Fraction(xs[i].first, 1)) {
                right[i] = vals[ind + 1].second;
            } else {
                Fraction a = vals[ind + 1].second, b = vals[ind + 2].second;
                Fraction d1 = vals[ind + 1].first - Fraction(xs[i].first, 1);
                Fraction d2 = vals[ind + 2].first - vals[ind + 1].first;
                right[i] = a + (a - b) * d1 / d2;
            }
        }
        right.back() = Fraction(0, 1);

        Fraction area(0, 1);
        for (size_t i = 0; i < left.size() - 1; i++) {
            Fraction d = Fraction(xs[i + 1].first - xs[i].first, 1);
            area = area + d * (right[i] + left[i + 1]) / Fraction(2, 1);
        }
        cout << "! " << (long long)area.num << " " << (long long)area.den << endl;
        fflush(stdout);
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

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

output:

? 1 1
? 1 0

result:

wrong answer Integer parameter [name=y] equals to 0, violates the range [1, 1000] (test case 1)