Submission #949042

#TimeUsernameProblemLanguageResultExecution timeMemory
949042rainboy초록색 삼각형 (YDX13_green)C11
1 / 1
629 ms600 KiB
#include <stdio.h> #define N 2000 typedef __int128_t L; unsigned int Z = 12345; int rand_() { return (Z *= 3) >> 1; } int xx[N], yy[N]; long long cross2(int i, int j) { return (long long) xx[i] * yy[j] - (long long) xx[j] * yy[i]; } long long cross(int i, int j, int k) { return (long long) (xx[j] - xx[i]) * (yy[k] - yy[i]) - (long long) (xx[k] - xx[i]) * (yy[j] - yy[i]); } int o; int compare(int i, int j) { int sgni, sgnj; long long c; sgni = xx[i] < xx[o] || xx[i] == xx[o] && yy[i] < yy[o] ? -1 : 1; sgnj = xx[j] < xx[o] || xx[j] == xx[o] && yy[j] < yy[o] ? -1 : 1; if (sgni != sgnj) return sgni - sgnj; c = cross(o, i, j); return c == 0 ? 0 : (c < 0 ? -1 : 1); } void sort(int *jj, int l, int r) { while (l < r) { int i = l, j = l, k = r, j_ = jj[l + rand_() % (r - l)], tmp; while (j < k) { int c = compare(jj[j], j_); if (c == 0) j++; else if (c < 0) { tmp = jj[i], jj[i] = jj[j], jj[j] = tmp; i++, j++; } else { k--; tmp = jj[j], jj[j] = jj[k], jj[k] = tmp; } } sort(jj, l, i); l = k; } } int main() { static int jj[N]; int n, n_, i, j, k; L ans; scanf("%d", &n); if (n <= 2) { printf("0\n"); return 0; } for (i = 0; i < n; i++) scanf("%d%d", &xx[i], &yy[i]); ans = 0; for (i = 0; i < n; i++) { n_ = 0; for (j = 0; j < n; j++) if (j != i) jj[n_++] = j; o = i, sort(jj, 0, n_); for (j = 0, k = 0; j < n_; j++) { while (k < j + n_ && cross(o, jj[j % n_], jj[k % n_]) <= 0) k++; ans += (L) (k - j - 1) * cross2(jj[j % n_], o); } } printf("%.12f\n", (double) ans / 2 / ((long long) n * (n - 1) * (n - 2) / 6)); return 0; }

Compilation message (stderr)

C.c: In function 'compare':
C.c:29:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   29 |  sgni = xx[i] < xx[o] || xx[i] == xx[o] && yy[i] < yy[o] ? -1 : 1;
      |                          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
C.c:30:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   30 |  sgnj = xx[j] < xx[o] || xx[j] == xx[o] && yy[j] < yy[o] ? -1 : 1;
      |                          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
C.c: In function 'main':
C.c:64:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
C.c:70:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...