QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#893300#9804. Guess the Polygonucup-team134Compile Error//Python35.0kb2025-02-10 17:09:432025-02-10 17:09:44

Judging History

This is the latest submission verdict.

  • [2025-02-10 17:09:44]
  • Judged
  • [2025-02-10 17:09:43]
  • Submitted

answer

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

using namespace std;

struct Fraction {
    long long num, den;
    Fraction(long long n = 0, long long d = 1) {
        long long 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 << "? " << k.num << " " << 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 << "! " << area.num << " " << area.den << endl;
        fflush(stdout);
    }
    return 0;
}

详细

  File "answer.code", line 6
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax