結果

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

テストケース

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

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#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<int, int>> ds;
    auto dfs = [&](auto dfs, int ld, int ln, int rd, int rn) -> bool {
        int md = ld + rd, mn = ln + rn;
        if (md > M) return false;
        ds.emplace_back(md, mn);
        if (ds.size() == N / 8) return true;
        if (dfs(dfs, ld, ln, md, mn)) return true;
        if (dfs(dfs, md, mn, rd, rn)) return true;
        return false;
    };
    assert(dfs(dfs, 1, 0, 1, 1));

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

    std::cout << 8 * ds.size() << '\n';

    int 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;
                if (j == 0) std::swap(x, y);
            }
            std::reverse(ds.begin(), ds.end());
        }
    }
    std::cout.flush();

    return 0;
}
0