結果

問題 No.5009 Draw A Convex Polygon
ユーザー t33ft33f
提出日時 2022-12-02 23:56:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,106 bytes
コンパイル時間 1,571 ms
実行使用メモリ 21,868 KB
スコア 0
平均クエリ数 1000000.00
最終ジャッジ日時 2022-12-02 23:56:40
合計ジャッジ時間 3,444 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int main() {
    struct P { int n, d; P(int _n, int _d) : n(_n), d(_d) {} };
    auto compare = [] (const P &lhs, const P &rhs) {
        return max(lhs.n, lhs.d) > max(rhs.n, rhs.d);
    };
    priority_queue<P, vector<P>, decltype(compare)> pq(compare);
    pq.emplace(0, 1);
    vector<P> v;
    while (v.size() < 250000) {
        const P p = pq.top();
        pq.pop();
        v.push_back(p);
        const auto [n, d] = p;
        assert(gcd(n, d) == 1);
        if (n > 0) pq.emplace(n, d + n);
        pq.emplace(d + n, d);
    }
    sort(v.begin(), v.end(), [](const P &lhs, const P &rhs) {
        return lhs.n * rhs.d < rhs.n * lhs.d;
    });
    int x = 0, y = 0;
    for (auto [n, d] : v) x -= d, y += n, cout << x << ' ' << y << '\n';
    for (auto [n, d] : v) x -= n, y -= d, cout << x << ' ' << y << '\n';
    for (auto [n, d] : v) x += d, y -= n, cout << x << ' ' << y << '\n';
    for (auto [n, d] : v) x += n, y += d, cout << x << ' ' << y << '\n';
}
0