結果

問題 No.5009 Draw A Convex Polygon
ユーザー merom686merom686
提出日時 2022-12-02 02:22:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 949 ms / 2,600 ms
コード長 1,185 bytes
コンパイル時間 2,152 ms
実行使用メモリ 21,880 KB
スコア 1,000,000
平均クエリ数 1000001.00
最終ジャッジ日時 2022-12-02 02:23:05
合計ジャッジ時間 4,836 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    int x, y;
};

int main() {
    int n = 641, m = 1000000 / 8 - 1;

    vector<P> p;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (gcd(i, j) != 1) continue;
            p.push_back({ i, j });
        }
    }
    sort(p.begin(), p.end(), [&](const P &p0, const P &p1) {
        return p0.x + p0.y > p1.x + p1.y;
    });
    p.resize(m);
    sort(p.begin(), p.end(), [&](const P &p0, const P &p1) {
        return p1.x * p0.y > p0.x * p1.y;
    });

    cout << (m + 1) * 8 << '\n';

    int x = 80326896, y = 0;
    for (int h = 0; h < 4; h++) {
        auto f = [&](int dx, int dy) {
            cout << x << ' ' << y << '\n';
            for (int i = 0; i < h; i++) {
                int t = dx;
                dx = -dy;
                dy = t;
            }
            x += dx;
            y += dy;
        };
        f(0, 1);
        for (int i = 0; i < m; i++) {
            f(-p[i].x, p[i].y);
        }
        f(-1, 1);
        for (int i = m - 1; i >= 0; i--) {
            f(-p[i].y, p[i].x);
        }
    }
    cout << flush;

    return 0;
}
0