#pragma GCC optimize ( "O3" ) #pragma GCC target ( "avx" ) #include using namespace std; #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE #define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define QUIT return 0 #define DEBUG1 #define DEBUG2 #define DEBUG3 cout << flush; // #define DEBUG1 \ // int x_prev1 = 0; \ // int y_prev1 = 0; \ // int x_prev2 = 1; \ // int y_prev2 = 1; \ // int count = 0; // #define DEBUG2 \ // if( j == 0 ){ \ // count += size; \ // } \ // if( x < - bound || bound < x ){ \ // cout << "WA (invalid x): (i,j) = (" << i << "," << j << ")\n"; \ // return 0; \ // } \ // if( y < - bound || bound < y ){ \ // cout << "WA (invalid x): (i,j) = (" << i << "," << j << ")\n"; \ // return 0; \ // } \ // using ll = long long; \ // if( ll( x - x_prev1 ) * ll( y_prev1 - y_prev2 ) == ll( x_prev1 - x_prev2 ) * ll( y - y_prev1 ) ){ \ // cout << "WA (linear): (i,j) = (" << i << "," << j << ")\n"; \ // return 0; \ // } \ // x_prev2 = x_prev1; \ // y_prev2 = y_prev1; \ // x_prev1 = x; \ // y_prev1 = y; \ // #define DEBUG3 assert( count == N ) \ int main() { UNTIE; // 10^9 - x >= x(x+1)/2 // -> x^2 + 3x - 2*10^9 <= 0 // -> -3/2 - sqrt(9 + 8*10^9)/2 <= x <= -3/2 + sqrt(9 + 8*10^9)/2 \approx 44719.8596 // 44719.8596 * 8 \approx 357758.877 CEXPR( int , N , ( 357758 / 8 - 1 ) * 8 + 4 ); cout << N << "\n"; CEXPR( int , N_8 , N / 8 ); CEXPR( int , bound , 1000000000 ); int x = bound; int y = 0; int dx; int dy; int dx_list[8] = { -1 , -1 , -N_8 - 1 , -1 , 1 , 1 , N_8 + 1 , 1 }; int dy_list[8] = { N_8 + 1 , 1 , -1 , -1 , -N_8 - 1 , -1 , 1 , 1 }; int ddx; int ddy; int ddx_list[8] = { 0 , -1 , 1 , 0 , 0 , 1 , -1 , 0 }; int ddy_list[8] = { -1 , 0 , 0 , -1 , 1 , 0 , 0 , 1 }; DEBUG1; int size; FOR( i , 0 , 8 ){ dx = dx_list[i]; dy = dy_list[i]; ddx = ddx_list[i]; ddy = ddy_list[i]; size = i % 2 == 1 ? N_8 + 1 : N_8; FOR( j , 0 , size ){ cout << x << " " << y << "\n"; DEBUG2; x += dx; y += dy; dx += ddx; dy += ddy; } } DEBUG3; QUIT; }