46G - Emperor's Problem - CodeForces Solution

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define N 82000
using namespace std;
struct ppp{
    int x,y;
    double k;
}ans[N];
int n,bo[N],choose[N],sx,sy,i,j,k,s;
pair<int,int> bo2[N];
bool cmp(const ppp&a,const ppp&b){
    return a.k<b.k;
}
int main(){
    scanf("%d",&n);
    for(i=0;i<=200;++i)
        for(j=0;j<=200;++j){
            bo[i*i+j*j]=1;
            bo2[i*i+j*j]=make_pair(i,j);
        }
    k=n; s=0;
    for(i=1;k;++i)if(bo[i])choose[i]=1,s+=i,k--;
    if(s&1){
        for(;;++i)if(bo[i]){
            choose[i]=1;
            s+=i;
            break;
        }
        for(;;--i)if(choose[i] && (s&1)==(i&1)){
            choose[i]=0;
            break;
        }
    }
    sx=sy=0;
    for(i=40000;i>=1;--i)if(choose[i]){
        int xx=bo2[i].first,yy=bo2[i].second;
        for(j=0;j<=1;++j)
            for(int px=-1;px<=1;++px)if(px)
                for(int py=-1;py<=1;++py)if(py){
                    int tx=sx+(j?xx*px:yy*px);
                    int ty=sy+(j?yy*py:xx*py);
                    if(1ll*tx*tx+1ll*ty*ty<=1ll*xx*xx+1ll*yy*yy){
                        sx=tx; sy=ty;
                        ans[++k].x=(j?xx*px:yy*px);
                        ans[k].y=(j?yy*py:xx*py);
                        ans[k].k=atan2(ans[k].y,ans[k].x);
                        goto ff;
                    }
                }
        ff:;
    }
    sort(ans+1,ans+n+1,cmp);
    sx=sy=0;
    printf("YES\n");
    for(i=1;i<=n;++i){
        sx+=ans[i].x;
        sy+=ans[i].y;
        printf("%d %d\n",sx,sy);
    }
}