結果

問題 No.5009 Draw A Convex Polygon
ユーザー t33ft33f
提出日時 2022-12-03 00:04:18
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 998 ms / 2,600 ms
コード長 1,157 bytes
コンパイル時間 1,051 ms
実行使用メモリ 21,756 KB
スコア 1,000,000
平均クエリ数 1000001.00
最終ジャッジ日時 2022-12-03 00:04:22
合計ジャッジ時間 3,938 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ（β）

テストケース

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

ソースコード

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;
    const int N = 1'000'000;
    while (v.size() < N / 4) {
        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;
    cout << N << '\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';
    for (auto [n, d] : v) x += d, y += n, cout << x << ' ' << y << '\n';
}
0