結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー |
|
提出日時 | 2022-12-04 00:04:32 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.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 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 |
ソースコード
#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;}