QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#797044 | #9804. Guess the Polygon | Chinese_zjc_ | WA | 1ms | 3816kb | C++14 | 2.3kb | 2024-12-02 14:54:41 | 2024-12-02 14:54:46 |
Judging History
answer
#include <bits/stdc++.h>
int T, n, cnt[1005];
long double L[1005], M[1005], R[1005];
long double query(int p, int eps = 0)
{
std::cout << "? " << p * 4 + eps << " 4" << std::endl;
long long a, b;
std::cin >> a >> b;
return 1.0l * a / b;
}
long double k(long double x1, long double y1, long double x2, long double y2, long double x)
{
return (x - x1) / (x2 - x1) * y2 + (x - x2) / (x1 - x2) * y1;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin >> T;
while (T--)
{
std::cin >> n;
std::fill(cnt, cnt + 1001, 0);
std::vector<int> app;
for (int i = 1, x, y; i <= n; ++i)
std::cin >> x >> y, ++cnt[x], app.push_back(x);
std::sort(app.begin(), app.end());
app.erase(std::unique(app.begin(), app.end()), app.end());
if (cnt[app[0]] == 1)
M[app[0]] = 0;
else
R[app[0]] = query(app[0], 1);
for (std::size_t i = 1; i + 1 < app.size(); ++i)
if (cnt[app[i]] == 1)
M[app[i]] = query(app[i]);
else
L[app[i]] = query(app[i], -1),
R[app[i]] = query(app[i], +1);
if (cnt[app.back()] == 1)
M[app.back()] = 0;
else
L[app.back()] = query(app.back(), -1);
long double sum = 0;
for (std::size_t i = 1; i < app.size(); ++i)
if (cnt[app[i - 1]] == 1 && cnt[app[i]] == 1)
sum += (M[app[i]] - M[app[i - 1]]) * (app[i] - app[i - 1]);
else if (cnt[app[i - 1]] == 1)
{
long double dx = (L[app[i]] - M[app[i - 1]]) / (app[i] - app[i - 1] - 0.25);
sum += (L[app[i]] + M[app[i - 1]] + dx / 4) * (app[i] - app[i - 1]);
}
else if (cnt[app[i]] == 1)
{
long double dx = (M[app[i]] - R[app[i - 1]]) / (app[i] - app[i - 1] - 0.25);
sum += (M[app[i]] + R[app[i - 1]] - dx / 4) * (app[i] - app[i - 1]);
}
else
sum += (L[app[i]] + R[app[i - 1]]) * (app[i] - app[i - 1]);
long long ans = static_cast<long long>(std::round(sum));
std::cout << "! " << (ans % 2 ? ans : ans / 2) << ' ' << (ans % 2 ? 2 : 1) << std::endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3816kb
input:
2 4 3 0 1 3 1 1 0 0 3 2 7 4 3 0 0 999 1000 1000 999 1999 1000
output:
? 3 4 ? 5 4 ! 3 1 ? 3996 4 ! 1995 2
result:
wrong answer the answer is incorrect, expect: 1999/2, find: 1995/2 (test case 2)