結果

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

テストケース

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

ソースコード

diff #

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

struct P {
    bool operator<(const P &p) const {
        return p.x * y > x * p.y;
    }
    int x, y;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 1000000, m = n / 8 - 1;

    vector<P> p(m);
    int k = 0;
    for (int w = 1; k < m; w++) {
        for (int i = 1;; i++) {
            int j = w - i;
            if (i >= j) break;
            if (gcd(i, j) != 1) continue;
            p[k++] = { i, j };
            if (k >= m) break;
        }
    }
    sort(p.begin(), p.end());

    cout << n << '\n';

    int x = 80106589, 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