結果

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

テストケース

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

ソースコード

diff # 

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

#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 

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 );
  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 };
  // int x_prev1 = 0;
  // int y_prev1 = 0;
  // int x_prev2 = 1;
  // int y_prev2 = 1;
  FOR( i , 0 , 8 ){
    dx = dx_list[i];
    dy = dy_list[i];
    ddx = ddx_list[i];
    ddy = ddy_list[i];
    FOR( j , 0 , N_8 ){
      cout << x << " " << y << "\n";
      // 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;
      // }
      // 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;
      x += dx;
      y += dy;
      dx += ddx;
      dy += ddy;
    }
  }
  cout << flush;
  QUIT;
}
0