QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#794949 | #9804. Guess the Polygon | ucup-team296# | WA | 1ms | 3616kb | C++20 | 2.8kb | 2024-11-30 17:03:23 | 2024-11-30 17:03:25 |
Judging History
answer
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct rat {
long p = 0, q = 1;
rat(long _p, long _q) {
long d = gcd(_p, _q);
p = _p / d;
q = _q / d;
}
rat(long x) {
p = x;
}
rat() {
}
rat operator + (rat x) const {
return {p * x.q + x.p * q, q * x.q};
}
rat operator - (rat x) const {
return {p * x.q - x.p * q, q * x.q};
}
rat operator * (rat x) const {
return {p * x.p, q * x.q};
}
rat operator / (rat x) const {
return {p * x.q, q * x.p};
}
};
struct test {
rat ask(rat x) {
cout << "? " << x.p << " " << x.q << endl;
int p, q;
cin >> p >> q;
return {p, q};
}
rat calc(rat y1, rat y2, rat x1, rat x2) {
rat m = {1, 2};
rat r = y1 + (m - x1) * (y2 - y1) / (x2 - x1);
return r;
}
void solve() {
int n;
cin >> n;
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
sort(x.begin(), x.end());
vector<pair<int, int>> xx;
for (int i = 0; i < n; i++) {
if (xx.empty() || x[i] > xx.back().first) {
xx.push_back({x[i], 1});
} else {
xx.back().second++;
}
}
int m = xx.size();
vector<rat> val(m, 0);
vector<rat> val2(m, 0);
for (int i = 0; i < m; i++) {
if (xx[i].second == 1) {
if (i > 0 && i < m - 1)
val[i] = ask(xx[i].first);
} else {
if (i > 0) {
val[i] = ask(rat(xx[i].first) - rat(1, 3));
}
if (i < m - 1) {
val2[i] = ask(rat(xx[i].first) + rat(1, 3));
}
}
}
rat res = 0;
for (int i = 0; i < m - 1; i++) {
rat x1, y1, x2, y2;
if (xx[i].second == 1) {
x1 = 0;
y1 = val[i];
} else {
x1 = {1, 3};
y1 = val2[i];
}
if (xx[i + 1].second == 1) {
x2 = 1;
y2 = val[i + 1];
} else {
x2 = {2, 3};
y2 = val[i + 1];
}
res = res + calc(y1, y2, x1, x2) * (xx[i + 1].first - xx[i].first);
}
// res = res * rat(1, 2);
cout << "! " << res.p << " " << res.q << endl;
}
};
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
test().solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3616kb
input:
2 4 3 0 1 3 1 1 0 0 4 3 5 3
output:
? 2 3 ? 4 3 ! 7 2
result:
wrong answer the answer is incorrect, expect: 3/1, find: 7/2 (test case 1)