QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#815847#9804. Guess the Polygonucup-team1769#WA 1ms3836kbC++203.5kb2024-12-15 17:50:032024-12-15 17:50:04

Judging History

This is the latest submission verdict.

  • [2024-12-15 17:50:04]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3836kb
  • [2024-12-15 17:50:03]
  • Submitted

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)