結果

問題 No.5009 Draw A Convex Polygon
ユーザー baLoon8128baLoon8128
提出日時 2022-12-05 00:36:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 872 ms / 2,600 ms
コード長 1,453 bytes
コンパイル時間 4,137 ms
実行使用メモリ 40,596 KB
スコア 1,000,000
平均クエリ数 909092.00
最終ジャッジ日時 2022-12-05 00:36:29
合計ジャッジ時間 6,708 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define repr(i, n) for (int i = (int)(n - 1); i >= 0; --i)

void rotate(pll &z) {
    z.second = exchange(z.first, -z.second);
}
pll operator+(const pll &a, const pll &b) {
    return {a.first + b.first, a.second + b.second};
}
pll operator-(const pll &a, const pll &b) {
    return {a.first - b.first, a.second - b.second};
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    vector<pll> q;
    for (int x = 1; x < 1000; x++) {
        for (int y = 1; y < x; y++) {
            if (gcd(x, y) == 1) q.emplace_back(x, y);
        }
    }
    sort(q.begin(), q.end(), [](auto a, auto b) { return a.second * b.first < a.first * b.second; });
    int n = 1000000;
    // int n;
    // cin >> n;
    q.resize(n / 4);
    pll cur = pll(0, 0);
    vector<pll> ret;
    rep(k, 4) {
        rep(i, n / 4) {
            ret.push_back(cur);
            cur = cur + q[i];
        }
        rep(i, n / 4) rotate(q[i]);
    }
    ll mx = 0, my = 0;
    for (auto [x, y] : ret) {
        mx = min(mx, x);
        my = min(my, y);
    }
    ll LM = 1000000000;
    cout << n << '\n';
    for (auto [x, y] : ret) {
        cout << x - mx - LM << " " << y - my - LM << '\n';
    }
    return 0;
}
0