QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#893300 | #9804. Guess the Polygon | ucup-team134 | Compile Error | / | / | Python3 | 5.0kb | 2025-02-10 17:09:43 | 2025-02-10 17:09:44 |
Judging History
This is the latest submission verdict.
- [2025-02-10 17:09:44]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [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