結果

問題 No.5009 Draw A Convex Polygon
ユーザー ra5anchorra5anchor
提出日時 2024-07-17 23:13:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,200 ms / 2,600 ms
コード長 1,140 bytes
コンパイル時間 1,244 ms
コンパイル使用メモリ 114,784 KB
実行使用メモリ 115,056 KB
スコア 1,000,000
最終ジャッジ日時 2024-07-17 23:13:34
合計ジャッジ時間 5,888 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <set>
#include <cmath>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

int main() {
    const int N = 1000000;
    set<tuple<double, int, int>> st;
    bool ok = false;
    
    for (int i = 1; i < 1300; ++i) {
        for (int j = 1; j < 1300; ++j) {
            int g = __gcd(i, j);
            st.emplace(atan2(static_cast<double>(j) / g, static_cast<double>(i) / g), i / g, j / g);
            if (st.size() == N) {
                ok = true;
                break;
            }
        }
        if (ok) {
            break;
        }
    }

    vector<tuple<double, int, int>> L(st.begin(), st.end());
    sort(L.begin(), L.end());

    vector<pair<long long, long long>> ans;
    long long nowx = -1000000000 + 1;
    long long nowy = -1000000000 + 1;

    for (int i = 0; i < N; ++i) {
        int x = get<1>(L[i]);
        int y = get<2>(L[i]);
        nowx += x;
        nowy += y;
        ans.emplace_back(nowx, nowy);
    }

    cout << N << '\n';
    for (int i = 0; i < N; ++i) {
        cout << ans[i].first << " " << ans[i].second << '\n';
    }

    return 0;
}
0