QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#815847 | #9804. Guess the Polygon | ucup-team1769# | WA | 1ms | 3836kb | C++20 | 3.5kb | 2024-12-15 17:50:03 | 2024-12-15 17:50:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define max_len 1200
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 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);
}
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(int fz, int fm)
{
cout << "? " << fz << " " << 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<int, 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);
int last_x = poi_vec[0].first;
if(poi_vec[0].second.size() != 1)
{
last_bian_len = vec_ji_cha(poi_vec[0].second);
}
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, 1);
if(y_diff_th == vec_ji_cha(y_vec))
{
ans_m2 = ans_m2 + (y_diff_th + last_bian_len) * (now_x - last_x);
last_x = now_x;
last_bian_len = y_diff_th.fz;
}
else if(y_diff_th < vec_ji_cha(y_vec))
{
ans_m2 = ans_m2 + (last_bian_len + vec_ji_cha(y_vec)) * (now_x - last_x);
last_x = now_x;
last_bian_len = y_diff_th;
}
else // vec_ji_cha(y_vec) < y_diff_th
{
ans_m2 = ans_m2 + (y_diff_th + last_bian_len) * (now_x - last_x);
last_x = now_x;
last_bian_len = y_diff_th + (-vec_ji_cha(y_vec));
}
last_jicha = vec_ji_cha(y_vec);
}
{
auto [now_x, y_vec] = poi_vec.back();
{
auto end_b = frac_num(0, 1);
if(last_jicha == 0)
{
ans_m2 = ans_m2 + (last_bian_len) * (now_x - last_x);
}
else
ans_m2 = ans_m2 + (last_bian_len + vec_ji_cha(y_vec)) * (now_x - last_x);
}
}
ans_m2.fm *= 2;
print_ans(ans_m2);
}
int main()
{
int T;
cin >> T;
while (T--)
{
sol();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
input:
2 4 3 0 1 3 1 1 0 0 2 1 3 0 0 999 1000 1000 999 1999 1000
output:
? 1 1 ! 3 1 ? 999 1 ! 1999 2
result:
ok correct! (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3836kb
input:
9 4 1 1 1 3 3 0 0 0 3 1 4 0 0 1 3 1 1 3 0 3 1
output:
? 1 1 ! 5 2 ? 1 1 ! 5 2
result:
wrong answer the answer is incorrect, expect: 7/2, find: 5/2 (test case 2)