結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー | chro_96 |
提出日時 | 2022-12-02 01:17:05 |
言語 | C (gcc 12.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,855 bytes |
コンパイル時間 | 325 ms |
実行使用メモリ | 33,460 KB |
スコア | 0 |
平均クエリ数 | 1000001.00 |
最終ジャッジ日時 | 2022-12-02 01:17:14 |
合計ジャッジ時間 | 4,249 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
ソースコード
#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 = 1; int sum = 2; long long a[1000000][2] = {}; int n = 0; long long tmp = 0LL; long long x = 1000000000LL; long long y = 0LL; a[0][0] = 0LL; a[0][1] = 1LL; 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; }