This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |