結果

問題 No.5009 Draw A Convex Polygon
ユーザー Nachia
提出日時 2022-12-02 00:14:07
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,578 bytes
コンパイル時間 1,218 ms
実行使用メモリ 39,040 KB
スコア 0
平均クエリ数 1001745.00
最終ジャッジ日時 2022-12-02 00:14:18
合計ジャッジ時間 2,762 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1
権限があれば一括ダウンロードができます

ソースコード

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 d=1; Fracs.size() < 250000; d++) for(int j=1; j<d; j++) if(GCD(d,j) == 1) Fracs.push_back({ d-j, j });
    sort(Fracs.begin(), Fracs.end());
    vector<std::pair<i64, i64>> points;
    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