結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 };

constexpr std::size_t N = 1000000;
constexpr int M = 641;

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 <= M) {
            ds.emplace_back(md, mn);
            if (ds.size() == N / 8) return;
            dfs(dfs, ld, ln, md, mn);
            if (ds.size() == N / 8) return;
            dfs(dfs, md, mn, rd, rn);
        }
    };
    dfs(dfs, 1, 0, 1, 1);

    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 << 8 * ds.size() << '\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::reverse(ds.begin(), ds.end());
        }
    }
    std::cout.flush();

    return 0;
}
0