oj.uz

답안 #545874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545874 2022-04-05T15:43:21 Z rainboy Printed Circuit Board (CEOI12_circuit) C
85 / 100
 100 ms 9184 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N	200000
 
unsigned int X = 12345;
 
int rand_() {
	return (X *= 3) >> 1;
}
 
long long cross2(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}
 
int xx[N], yy[N], ii[N * 2];
 
long long cross(int i, int j, int k) {
	return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}
 
int compare(const void *a, const void *b) {
	int h1 = *(int *) a;
	int h2 = *(int *) b;
	long long c = cross2(xx[ii[h1]], yy[ii[h1]], xx[ii[h2]], yy[ii[h2]]);
 
	return c ? (c < 0 ? -1 : 1) : (h1 & 1) - (h2 & 1);
}
 
int iq[1 + N], pq[N], cnt, x_, y_;
 
double t(int i, int j) {
	return (double) cross2(xx[i], yy[i], xx[j] - xx[i], yy[j] - yy[i]) / cross2(x_, y_, xx[j] - xx[i], yy[j] - yy[i]);
}
 
int lt(int i, int j) {
	double t1 = t(ii[i << 1 | 0], ii[i << 1 | 1]), t2 = t(ii[j << 1 | 0], ii[j << 1 | 1]);
 
	if (t1 != t2)
		return t1 < t2;
	return cross(ii[i << 1 | 0], ii[j << 1 | 0], ii[j << 1 | 1]) < 0 || cross(ii[i << 1 | 1], ii[j << 1 | 0], ii[j << 1 | 1]) < 0;
}
 
int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
 
void pq_up(int i) {
	int p, q, j;
 
	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}
 
void pq_dn(int i) {
	int p, q, j;
 
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}
 
void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}
 
void pq_remove(int i) {
	if (pq[i]) {
		int j = iq[cnt--];
 
		if (j != i)
			pq[j] = pq[i], pq_up(j), pq_dn(j);
		pq[i] = 0;
	}
}
 
int main() {
	static int hh[N * 2];
	static char visible[N];
	int n, n_, g, h, h_, i;
 
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	n_ = 0;
	for (i = 0; i < n; i++) {
		long long c = cross2(xx[i], yy[i], xx[(i + 1) % n], yy[(i + 1) % n]);
 
		if (c < 0) {
			ii[i << 1 | 0] = i, ii[i << 1 | 1] = (i + 1) % n;
			hh[n_++] = i << 1 | 0, hh[n_++] = i << 1 | 1;
		} else if (c > 0) {
			ii[i << 1 | 0] = (i + 1) % n, ii[i << 1 | 1] = i;
			hh[n_++] = i << 1 | 0, hh[n_++] = i << 1 | 1;
		}
	}
	qsort(hh, n_, sizeof *hh, compare);
	memset(visible, 1, n * sizeof *visible);
	for (h = 0; h < n_; h++) {
		h_ = hh[h];
		x_ = xx[ii[h_]], y_ = yy[ii[h_]];
		if ((h_ & 1) == 0)
			pq_add(h_ >> 1);
		else
			pq_remove(h_ >> 1);
		if (cnt) {
			i = iq[1];
			if (cross(ii[i << 1 | 0], ii[i << 1 | 1], ii[h_]) > 0)
				visible[ii[h_]] = 0;
		}
	}
	for (h = 0; h < n_; h = h_) {
		int h1, i_;
 
		h1 = hh[h], h_ = h, i_ = -1;
		while (h_ < n_ && cross2(xx[ii[h1]], yy[ii[h1]], xx[ii[hh[h_]]], yy[ii[hh[h_]]]) == 0) {
			i = ii[hh[h_++]];
			if (i_ == -1 || xx[i_] > xx[i])
				i_ = i;
		}
		for (g = h; g < h_; g++) {
			i = ii[hh[g]];
			if (i != i_)
				visible[i] = 0;
		}
	}
	cnt = 0;
	for (i = 0; i < n; i++)
		if (visible[i])
			cnt++;
	printf("%d\n", cnt);
	for (i = 0; i < n; i++)
		if (visible[i])
			printf("%d ", i + 1);
	printf("\n");
	return 0;
}

Compilation message

circuit.c: In function 'main':
circuit.c:84:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
circuit.c:86:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
85.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 7 ms 724 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 20 ms 1108 KB Output is correct
8 Correct 8 ms 724 KB Output is correct
9 Correct 8 ms 724 KB Output is correct
10 Correct 10 ms 724 KB Output is correct
11 Correct 8 ms 852 KB Output is correct
12 Correct 11 ms 1152 KB Output is correct
13 Correct 22 ms 1632 KB Output is correct
14 Correct 23 ms 1960 KB Output is correct
15 Correct 27 ms 2380 KB Output is correct
16 Correct 55 ms 4712 KB Output is correct
17 Correct 79 ms 4792 KB Output is correct
18 Execution timed out 125 ms 8912 KB Time limit exceeded
19 Execution timed out 126 ms 9052 KB Time limit exceeded
20 Execution timed out 171 ms 9184 KB Time limit exceeded