Submission #544774

#	Time	Username	Problem	Language	Result	Execution time	Memory
544774		rainboy	Tri (CEOI09_tri)	C11	100 / 100	240 ms	30516 KiB

tri

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000
#define N_	(1 << 17)

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int xx[N], yy[N], n;

long long cross2(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

long long cross3(int x0, int y0, int x1, int y1, int x2, int y2) {
	return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}

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]);
}

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			long long c = cross2(xx[ii[j]], yy[ii[j]], xx[i_], yy[i_]);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ii_[N], cnt;

int merge(int *ii1, int cnt1, int *ii2, int cnt2, int sign) {
	int h1, h2;

	h1 = h2 = 0, cnt = 0;
	while (h1 < cnt1 && h2 < cnt2) {
		int c = xx[ii1[h1]] != xx[ii2[h2]] ? xx[ii1[h1]] - xx[ii2[h2]] : yy[ii1[h1]] - yy[ii2[h2]], i;

		if (c < 0)
			i = ii1[h1++];
		else if (c > 0)
			i = ii2[h2++];
		else
			i = ii1[h1], h1++, h2++;
		while (cnt >= 2 && cross(ii_[cnt - 2], ii_[cnt - 1], i) * sign >= 0)
			cnt--;
		ii_[cnt++] = i;
	}
	while (h1 < cnt1) {
		int i = ii1[h1++];

		while (cnt >= 2 && cross(ii_[cnt - 2], ii_[cnt - 1], i) * sign >= 0)
			cnt--;
		ii_[cnt++] = i;
	}
	while (h2 < cnt2) {
		int i = ii2[h2++];

		while (cnt >= 2 && cross(ii_[cnt - 2], ii_[cnt - 1], i) * sign >= 0)
			cnt--;
		ii_[cnt++] = i;
	}
	return cnt;
}

int ii[N], *iiu[N_ * 2], *iid[N_ * 2], kku[N_ * 2], kkd[N_ * 2], n_;

void build(int n) {
	int i;

	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++) {
		iiu[n_ + i] = (int *) malloc(1 * sizeof *iiu[n_ + i]);
		iid[n_ + i] = (int *) malloc(1 * sizeof *iid[n_ + i]);
		if (i < n)
			iiu[n_ + i][kku[n_ + i]++] = iid[n_ + i][kkd[n_ + i]++] = ii[i];
	}
	for (i = n_ - 1; i > 0; i--) {
		kku[i] = merge(iiu[i << 1 | 0], kku[i << 1 | 0], iiu[i << 1 | 1], kku[i << 1 | 1], 1);
		iiu[i] = (int *) malloc(kku[i] * sizeof *iiu[i]);
		memcpy(iiu[i], ii_, kku[i] * sizeof *ii_);
		kkd[i] = merge(iid[i << 1 | 0], kkd[i << 1 | 0], iid[i << 1 | 1], kkd[i << 1 | 1], -1);
		iid[i] = (int *) malloc(kkd[i] * sizeof *iid[i]);
		memcpy(iid[i], ii_, kkd[i] * sizeof *ii_);
	}
}

int search(int x, int y) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (cross2(xx[ii[h]], yy[ii[h]], x, y) < 0)
			lower = h;
		else
			upper = h;
	}
	return lower;
}

int query_(int i, int x1, int y1, int x2, int y2) {
	int lower, upper;

	if (x1 < x2) {
		lower = -1, upper = kkd[i];
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;

			if (cross3(x1, y1, x2, y2, xx[iid[i][h]], yy[iid[i][h]]) < 0)
				return 1;
			if (h + 1 < kkd[i] && cross2(x2 - x1, y2 - y1, xx[iid[i][h + 1]] - xx[iid[i][h]], yy[iid[i][h + 1]] - yy[iid[i][h]]) < 0)
				lower = h;
			else
				upper = h;
		}
	} else {
		lower = -1, upper = kku[i];
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;

			if (cross3(x1, y1, x2, y2, xx[iiu[i][h]], yy[iiu[i][h]]) < 0)
				return 1;
			if (h + 1 < kku[i] && cross2(x2 - x1, y2 - y1, xx[iiu[i][h + 1]] - xx[iiu[i][h]], yy[iiu[i][h + 1]] - yy[iiu[i][h]]) < 0)
				lower = h;
			else
				upper = h;
		}
	}
	return 0;
}

int query(int l, int r, int x1, int y1, int x2, int y2) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1 && query_(l++, x1, y1, x2, y2))
			return 1;
		if ((r & 1) == 0 && query_(r--, x1, y1, x2, y2))
			return 1;
	}
	return 0;
}

int main() {
	int q, i;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	build(n);
	while (q--) {
		int x1, y1, x2, y2, tmp, l, r;

		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		if (cross2(x1, y1, x2, y2) > 0)
			tmp = x1, x1 = x2, x2 = tmp, tmp = y1, y1 = y2, y2 = tmp;
		l = search(x1, y1) + 1;
		r = search(x2, y2);
		printf(l <= r && query(l, r, x1, y1, x2, y2) ? "Y\n" : "N\n");
	}
	return 0;
}

Compilation message (stderr)

tri.c: In function 'main':
tri.c:171:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
tri.c:173:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tri.c:178:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |   scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100