結果

問題 No.5009 Draw A Convex Polygon
ユーザー suisensuisen
提出日時 2022-12-03 23:54:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,369 bytes
コンパイル時間 745 ms
実行使用メモリ 21,964 KB
スコア 0
平均クエリ数 1000001.00
最終ジャッジ日時 2022-12-03 23:54:11
合計ジャッジ時間 4,153 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge16
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <vector>

constexpr int sgn_x[4] = { +1, -1, -1, +1 };
constexpr int sgn_y[4] = { +1, +1, -1, -1 };

int main() {
    std::vector<std::pair<long long, long long>> ds;
    auto dfs = [&](auto dfs, int ld, int ln, int rd, int rn) -> void {
        int md = ld + rd;
        int mn = ln + rn;
        if (md <= 641) {
            ds.emplace_back(md, mn);
            if (ds.size() == 125000) return;
            dfs(dfs, ld, ln, md, mn);
            if (ds.size() == 125000) return;
            dfs(dfs, md, mn, rd, rn);
        }
    };
    dfs(dfs, 1, 0, 1, 1);

    long long sd = 0, sn = 0;
    for (auto& [d, n] : ds) {
        sd += d;
        sn += n;
    }

    std::sort(
        ds.begin(),
        ds.end(),
        [&](const std::pair<long long, long long>& p, const std::pair<long long, long long>& q) {
            auto [pd, pn] = p;
            auto [qd, qn] = q;
            return pn * qd < qn* pd;
        }
    );

    std::cout << 1000000 << '\n';

    long long cx = 0, cy = 0;

    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (auto& [x, y] : ds) {
                std::cout << cx << ' ' << cy << '\n';
                cx += sgn_x[i] * x, cy += sgn_y[i] * y;
                std::swap(x, y);
            }
        }
    }
    std::cout.flush();

    return 0;
}
0