結果

問題 No.5009 Draw A Convex Polygon
ユーザー chro_96chro_96
提出日時 2022-12-02 01:22:54
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 786 ms / 2,600 ms
コード長 1,821 bytes
コンパイル時間 178 ms
実行使用メモリ 33,748 KB
スコア 1,000,000
平均クエリ数 1000001.00
最終ジャッジ日時 2022-12-02 01:22:57
合計ジャッジ時間 2,694 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

int gcd (int a, int b) {
  if (b <= 0) {
    return a;
  }
  
  return gcd(b, a%b);
}

int cmp_r (const void *a, const void *b) {
  long long *a_ = (long long *)a;
  long long *b_ = (long long *)b;
  
  if (a_[0]*b_[1] < a_[1]*b_[0]) {
    return -1;
  }
  
  if (a_[0]*b_[1] > a_[1]*b_[0]) {
    return 1;
  }
  
  return 0;
}

int main () {
  int cnt = 0;
  int sum = 3;
  long long a[1000000][2] = {};
  
  int n = 0;
  long long tmp = 0LL;
  
  long long x = 1000000000LL;
  long long y = 0LL;
  
  while (cnt < 125000) {
    for (int i = 1; 2*i < sum; i++) {
      int j = sum-i;
      if (gcd(i, j) == 1) {
        a[cnt][0] = (long long)i;
        a[cnt][1] = (long long)j;
        cnt++;
      }
    }
    sum++;
  }
  
  while (n < 125000 && tmp+a[n][0]+a[n][1] <= 1000000000LL) {
    tmp += a[n][0]+a[n][1];
    n++;
  }
  
  qsort(a, n, sizeof(long long)*2, cmp_r);
  
  printf("%d\n", 8*n);
  for (int i = 0; i < n; i++) {
    x -= a[i][0];
    y += a[i][1];
    printf("%lld %lld\n", x, y);
  }
  for (int i = n-1; i >= 0; i--) {
    x -= a[i][1];
    y += a[i][0];
    printf("%lld %lld\n", x, y);
  }
  
  for (int i = 0; i < n; i++) {
    x -= a[i][1];
    y -= a[i][0];
    printf("%lld %lld\n", x, y);
  }
  for (int i = n-1; i >= 0; i--) {
    x -= a[i][0];
    y -= a[i][1];
    printf("%lld %lld\n", x, y);
  }
  
  for (int i = 0; i < n; i++) {
    x += a[i][0];
    y -= a[i][1];
    printf("%lld %lld\n", x, y);
  }
  for (int i = n-1; i >= 0; i--) {
    x += a[i][1];
    y -= a[i][0];
    printf("%lld %lld\n", x, y);
  }
  
  for (int i = 0; i < n; i++) {
    x += a[i][1];
    y += a[i][0];
    printf("%lld %lld\n", x, y);
  }
  for (int i = n-1; i >= 0; i--) {
    x += a[i][0];
    y += a[i][1];
    printf("%lld %lld\n", x, y);
  }
  
  return 0;
}
0