Submission #532358

#	Time	Username	Problem	Language	Result	Execution time	Memory
532358		rainboy	절취선 (JOI14_ho_t5)	C11	10 / 100	9 ms	592 KiB

2014_ho_t5

#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]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50