QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#815905 | #9804. Guess the Polygon | lzz | WA | 1ms | 3772kb | C++20 | 3.8kb | 2024-12-15 18:36:26 | 2024-12-15 18:36:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define max_len 1200
#define int int64_t
struct frac_num
{
int fz, fm;
frac_num() = default;
frac_num(int zz, int mm)
{
fz = zz, fm = mm;
mk_gcd();
}
frac_num(int zz)
{
fz = zz, fm = 1;
}
void mk_gcd()
{
int g = gcd(fz, fm);
fz = fz / g, fm = fm / g;
}
frac_num operator+(const frac_num&r) const
{
return frac_num(fz * r.fm + fm * r.fz, fm * r.fm);
}
frac_num operator-(const frac_num&r) const
{
return frac_num(fz * r.fm - fm * r.fz, fm * r.fm);
}
frac_num operator+(const int&r) const
{
return frac_num(fz + fm * r, fm);
}
frac_num operator-(const int&r) const
{
return frac_num(fz - fm * r, fm);
}
frac_num operator*(const frac_num&r) const
{
return frac_num(fz * r.fz, fm * r.fm);
}
frac_num operator*(const int r) const
{
return frac_num(fz * r, fm);
}
frac_num operator/(const int r) const
{
return frac_num(fz, fm * r);
}
bool operator==(const int r) const
{
return fm == 1 && fz == r;
}
bool operator<(const int r) const
{
return 1.0 * fz / fm < r;
}
bool operator<(const frac_num&r) const
{
return fz * r.fm < fm * r.fz;
}
};
frac_num print_ques(frac_num fn)
{
fn.mk_gcd();
cout << "? " << fn.fz << " " << fn.fm << endl;
int zz, mm;
cin >> zz >> mm;
return frac_num(zz, mm);
}
void print_ans(frac_num fn)
{
fn.mk_gcd();
cout << "! " << fn.fz << " " << fn.fm << endl;
}
int N;
map<int, set<int>> poi_map;
void input()
{
poi_map.clear();
cin >> N;
for (int i = 0; i < N; i++)
{
int x, y;
cin >> x >> y;
poi_map[x].insert(y);
}
}
int vec_ji_cha(vector<int> vec)
{
return vec.back() - vec.front();
}
void sol()
{
input();
// x, [y]
vector<pair<frac_num, vector<int>>> poi_vec;
for(auto [pir_x, pirs] : poi_map)
{
poi_vec.push_back({pir_x, vector<int>()});
for(auto yy : pirs)
{
poi_vec.back().second.push_back(yy);
}
}
int poi_su = poi_vec.size();
frac_num ans_m2 = 0;
frac_num last_bian_len = frac_num(0, 1);
frac_num last_x = poi_vec[0].first;
if(poi_vec[0].second.size() > 1)
{
last_bian_len = print_ques(last_x);
}
// int last_jicha = 0;
for (int i = 1; i < poi_su - 1; i++)
{
auto [now_x, y_vec] = poi_vec[i];
auto y_diff_th = print_ques(now_x);
if(y_vec.size() == 1)
{
ans_m2 = ans_m2 + (y_diff_th + last_bian_len) * (now_x - last_x);
last_x = now_x;
last_bian_len = y_diff_th;
}
else
{
ans_m2 = ans_m2 + (y_diff_th + last_bian_len) * (now_x - last_x);
auto mid_x = (now_x + poi_vec[i + 1].first) / 2;
auto y_diff_mid = print_ques(mid_x);
ans_m2 = ans_m2 + (y_diff_th + y_diff_mid) * (mid_x - now_x);
last_x = mid_x;
last_bian_len = y_diff_mid;
}
}
{
auto [now_x, y_vec] = poi_vec.back();
{
auto end_b = frac_num(0, 1);
if(y_vec.size() == 1)
{
ans_m2 = ans_m2 + (last_bian_len) * (now_x - last_x);
}
else
{
auto y_diff_mid = print_ques(now_x);
ans_m2 = ans_m2 + (last_bian_len + y_diff_mid) * (now_x - last_x);
}
}
}
ans_m2.fm *= 2;
print_ans(ans_m2);
}
int32_t main()
{
int T;
cin >> T;
while (T--)
{
sol();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3772kb
input:
2 4 3 0 1 3 1 1 0 0 2 1 1 1 3 0 0 999 1000 1000 999 1999 1000
output:
? 1 1 ? 2 1 ! 3 1 ? 999 1 ! 1999 2
result:
ok correct! (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3612kb
input:
9 4 1 1 1 3 3 0 0 0 3 1 1 2
output:
? 1 1 ? 2 1 ! 7 2
result:
wrong answer the answer is incorrect, expect: 5/2, find: 7/2 (test case 1)