結果

問題 No.5009 Draw A Convex Polygon
ユーザー karinohitokarinohito
提出日時 2022-12-02 01:14:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,740 ms / 2,600 ms
コード長 1,694 bytes
コンパイル時間 2,244 ms
実行使用メモリ 48,136 KB
スコア 1,000,000
平均クエリ数 977088.00
最終ジャッジ日時 2022-12-02 01:14:49
合計ジャッジ時間 6,526 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll mod=998244353;
using vll =vector<ll>;
using vvll =vector<vll>;
#define all(A) A.begin(),A.end()
#define rep(i,n) for(int i=0;i<n;i++)

ll sqrtz(ll N) {
    ll L = 0;
    ll R = sqrt(N)+10000;
    while (abs(R - L) > 1) {
        ll mid = (R +L) / 2;
        if (mid * mid <= N)L = mid;
        else R = mid;
    }
    return L;
    
}

ll gcd(ll(a), ll(b)) {
    if (a == 0)return b;
    if (b == 0)return a;
    ll c = a;
    while (a % b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return b;
}

int main(){
    vector<pair<ll,ll>> P;
    ll N=1e6/4;
    vector<pair<double,pair<ll,ll>>> G;
    for(ll i=1;i<=1200;i+=2){
        for(ll j=i+2;j<=1200;j+=2){
            ll g=gcd(i,j);
            if(g!=1)continue;
            G.push_back({double(i)/double(j),{i,j}});
            G.push_back({double(j)/double(i),{j,i}});
            if(G.size()==N)break;
        }
    }
    sort(all(G));
    //reverse(all(G));
    //cout<<G.size()<<endl;
    //return 0;
    P.push_back({-1e9+1,-1});
    rep(i,N-1){
        ll x=P.back().first;
        ll y=P.back().second;
        ll nx=x+G[i].second.first;
        ll ny=y-G[i].second.second;
        if(nx>0||ny<-1e9){
            cout<<"ERROR"<<endl;
            return 0;
        }
        P.push_back({nx,ny});
    }
    P.resize(N*4);
    //N=P.size();
    for(ll n=N-1;n>=0;n--){
        P[N+(N-n-1)]={-P[n].first,P[n].second};
    }

    //N=P.size();

    for(ll n=2*N-1;n>=0;n--){
        P[2*N+(2*N-n-1)]={P[n].first,-P[n].second};
    }

    cout<<P.size()<<endl;;
    rep(i,P.size())cout<<P[i].first<<" "<<P[i].second<<endl;
    return 0;
}
0