結果

問題 No.5009 Draw A Convex Polygon
ユーザー 👑 p-adicp-adic
提出日時 2022-12-02 02:14:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 310 ms / 2,600 ms
コード長 2,603 bytes
コンパイル時間 2,668 ms
実行使用メモリ 22,204 KB
スコア 357,748
平均クエリ数 357749.00
最終ジャッジ日時 2022-12-02 02:15:01
合計ジャッジ時間 4,083 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#pragma GCC optimize ( "O3" )
#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;

#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::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;
}
0