結果

問題 No.5009 Draw A Convex Polygon
ユーザー maimai
提出日時 2022-12-11 20:50:46
言語 cLay
(20240714-1)
結果
AC  
実行時間 820 ms / 2,600 ms
コード長 950 bytes
コンパイル時間 2,109 ms
実行使用メモリ 82,596 KB
スコア 10
平均クエリ数 11.00
最終ジャッジ日時 2022-12-11 20:50:51
合計ジャッジ時間 4,825 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

void check(const deque<pair<ll,ll>>& dq) {
  ll vy1 = dq[0].first-dq[1].first;
  ll vx1 = dq[0].second-dq[1].second;
  ll vy2 = dq[1].first-dq[2].first;
  ll vx2 = dq[1].second-dq[2].second;
  if (vy1*vx2 < vy2*vx1) {
    cout << vx1 << " " << vy1 << " " << vx2 << " " << vy2 << endl;
    abort();
  }
}

{
  set<pair<int, int>> li;
  
  REP(i, 1500) {
    const int vy = i + 1;
    REP(j, 1500) {
      const int vx = j + 1;
      int g = gcd(vy, vx);
      li.emplace(vy/g, vx/g);
    }
  }
  int n = 10;
  wt(n);
  n -= 2;
  ll y = 0, x = 0;
  // ll oy = 0, ox = 0;   
  ll oy = 500000000, ox = 500000000;
  wt(0-oy, 0-ox);
  auto it = li.begin();
  deque<pair<ll,ll>> q;
    q.emplace_back(0, 0);
  REP(_, n) {
    assert(it != li.end());
    y += it->first;
    x += it->second;
    wt(y-oy, x-ox);
    ++it;
    q.emplace_back(y, x);
    if (q.size() == 3) check(q);
    if (q.size() > 4) q.pop_front();
  }
  wt(0-oy, x-ox);
  cout.flush();
}
0