Submission #532358

#TimeUsernameProblemLanguageResultExecution timeMemory
532358rainboy절취선 (JOI14_ho_t5)C11
10 / 100
9 ms592 KiB
#include <stdio.h> #include <string.h> #define N 1004 int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } int ds[N]; int find(int i) { return ds[i] < 0 ? i : (ds[i] = find(ds[i])); } void join(int i, int j) { i = find(i); j = find(j); if (i == j) return; if (ds[i] > ds[j]) ds[i] = j; else { if (ds[i] == ds[j]) ds[i]--; ds[j] = i; } } int intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { int tmp; if (x1 > x2) tmp = x1, x1 = x2, x2 = tmp; if (y1 > y2) tmp = y1, y1 = y2, y2 = tmp; if (x3 > x4) tmp = x3, x3 = x4, x4 = tmp; if (y3 > y4) tmp = y3, y3 = y4, y4 = tmp; return max(x1, x3) <= min(x2, x4) && max(y1, y3) <= min(y2, y4); } int get_ve(int *xx, int *yy, int n) { int i, j, ve; ve = n; for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) if (intersect(xx[i << 1 | 0], yy[i << 1 | 0], xx[i << 1 | 1], yy[i << 1 | 1], xx[j << 1 | 0], yy[j << 1 | 0], xx[j << 1 | 1], yy[j << 1 | 1])) ve--; return ve; } int get_c(int *xx, int *yy, int n) { int i, j, c; memset(ds, -1, n * sizeof *ds); for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) if (intersect(xx[i << 1 | 0], yy[i << 1 | 0], xx[i << 1 | 1], yy[i << 1 | 1], xx[j << 1 | 0], yy[j << 1 | 0], xx[j << 1 | 1], yy[j << 1 | 1])) join(i, j); c = 0; for (i = 0; i < n; i++) if (ds[i] < 0) c++; return c; } int main() { static int xx[N * 2], yy[N * 2]; int w, h, n, i; scanf("%d%d%d", &w, &h, &n); for (i = 0; i < n * 2; i++) scanf("%d%d", &xx[i], &yy[i]); xx[n << 1 | 0] = 0, yy[n << 1 | 0] = 0, xx[n << 1 | 1] = w, yy[n << 1 | 1] = 0; xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h; xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h; xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0; n += 4; printf("%d\n", get_c(xx, yy, n) - get_ve(xx, yy, n)); return 0; }

Compilation message (stderr)

2014_ho_t5.c: In function 'main':
2014_ho_t5.c:77:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |     ~~^~~
2014_ho_t5.c:77:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                             ~~^~~
2014_ho_t5.c:77:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                                                     ~~^~~
2014_ho_t5.c:77:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   77 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                                                                             ~~^~~
2014_ho_t5.c:78:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |     ~~^~~
2014_ho_t5.c:78:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                             ~~^~~
2014_ho_t5.c:78:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                                                     ~~^~~
2014_ho_t5.c:78:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                                                                             ~~^~~
2014_ho_t5.c:79:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |     ~~^~~
2014_ho_t5.c:79:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                             ~~^~~
2014_ho_t5.c:79:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                                                     ~~^~~
2014_ho_t5.c:79:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                                                                             ~~^~~
2014_ho_t5.c:73:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d%d", &w, &h, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.c:75:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...