結果

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

テストケース

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

ソースコード

diff # 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;
using i64 = long long;


// please ensure x != 0
int LsbIndex(unsigned int x) noexcept {
    return __builtin_ctz(x);
}

unsigned int GCD(unsigned int a, unsigned int b) noexcept {
    if(!a || !b) return a|b;
    int q = LsbIndex(a|b);
    b >>= LsbIndex(b);
    a >>= LsbIndex(a);
    while(a!=b){
        if(a<b){ b-=a; b>>=LsbIndex(b); }
        else{ a-=b; a>>=LsbIndex(a); }
    }
    return a<<q;
};

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 && Fracs.size() < 250000; 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({ 102459, -75574918 });
    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();
    printf("%d\n", (int)points.size());
    for(auto [x,y] : points){
    	printf("%lld %lld\n", x, y);
    	assert(-75574918 <= x && x <= 75574917);
    	assert(-75574918 <= y && y <= 75574917);
    }
    return 0;
}
0