結果

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

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

i64 GCD(i64 a, i64 b){
    return b ? GCD(b,a%b) : a;
}

struct Frac{
    i64 a, b;
};

bool operator<(Frac l, Frac r){ return l.a * r.b < l.b * r.a; }

int main(){
    vector<Frac> Fracs;
    Fracs.push_back({ 0, 1 });
    for(int i=1; i<650; i++) for(int j=1; j<650; j++) if(GCD(i,j) == 1) Fracs.push_back({ i, j });
    sort(Fracs.begin(), Fracs.end());
    vector<std::pair<i64, i64>> points;
    Fracs.resize(250000);
    points.push_back({ 0, 0 });
    for(auto f : Fracs){ auto [x,y] = points.back(); points.push_back({ x+f.b, y+f.a }); }
    for(auto f : Fracs){ auto [x,y] = points.back(); points.push_back({ x-f.a, y+f.b }); }
    for(auto f : Fracs){ auto [x,y] = points.back(); points.push_back({ x-f.b, y-f.a }); }
    for(auto f : Fracs){ auto [x,y] = points.back(); points.push_back({ x+f.a, y-f.b }); }
    points.pop_back();
    cout << points.size() << '\n';
    i64 x = 0, y = 0;
    for(auto f : points){ x = min(x, f.first); }
    for(auto f : points){ y = min(y, f.second); }
    for(auto& f : points){ f.first -= x; f.second -= y; }
    for(auto f : points) cout << f.first << ' ' << f.second << '\n';
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0