Submission #924824

#	Time	Username	Problem	Language	Result	Execution time	Memory
924824		rainboy	먼 별 (KOI16_dist)	C11	100 / 100	154 ms	1888 KiB

dist

#include <stdio.h>

#define N	30000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

long long dot2(int x1, int y1, int x2, int y2) {
	return (long long) x1 * x2 + (long long) y1 * y2;
}

int xx[N], yy[N], ddx[N], ddy[N], xx_[N], yy_[N], n;

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 o;

int compare(int i, int j) {
	int ti, tj;
	long long c;

	ti = xx_[i] != xx_[o] ? (xx_[i] < xx_[o] ? 1 : 2) : (yy_[i] != yy_[o] ? (yy_[i] < yy_[o] ? 1 : 2) : 0);
	tj = xx_[j] != xx_[o] ? (xx_[j] < xx_[o] ? 1 : 2) : (yy_[j] != yy_[o] ? (yy_[j] < yy_[o] ? 1 : 2) : 0);
	if (ti != tj)
		return ti - tj;
	c = cross(o, i, j);
	if (c != 0)
		return c < 0 ? -1 : 1;
	return xx_[i] != xx_[j] ? xx_[i] - xx_[j] : yy_[i] - yy_[j];
}

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) {
			int c = compare(ii[j], 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 i_, j_;

long long solve() {
	static int ii[N];
	int cnt, h, h_, i;
	long long d, d_;

	o = -1;
	for (i = 0; i < n; i++)
		if (o == -1 || xx_[o] > xx_[i] || xx_[o] == xx_[i] && yy_[o] > yy_[i])
			o = i;
	for (i = 0; i < n; i++)
		ii[i] = i;
	ii[0] = o, ii[o] = 0;
	sort(ii, 1, n);
	cnt = 0;
	for (i = 0; i < n; i++) {
		if (cnt && compare(ii[cnt - 1], ii[i]) == 0)
			continue;
		while (cnt >= 2 && cross(ii[cnt - 2], ii[cnt - 1], ii[i]) >= 0)
			cnt--;
		ii[cnt++] = ii[i];
	}
	d_ = 0, i_ = j_ = -1;
	for (h = 0, h_ = 0; h < cnt; h++) {
		if (h_ == h)
			h_ = (h_ + 1) % cnt;
		while (cross2(xx_[ii[(h + 1) % cnt]] - xx_[ii[h]], yy_[ii[(h + 1) % cnt]] - yy_[ii[h]], xx_[ii[(h_ + 1) % cnt]] - xx_[ii[h_]], yy_[ii[(h_ + 1) % cnt]] - yy_[ii[h_]]) < 0)
			h_ = (h_ + 1) % cnt;
		d = dot2(xx_[ii[h_]] - xx_[ii[h]], yy_[ii[h_]] - yy_[ii[h]], xx_[ii[h_]] - xx_[ii[h]], yy_[ii[h_]] - yy_[ii[h]]);
		if (d_ < d)
			d_ = d, i_ = ii[h], j_ = ii[h_];
	}
	return d_;
}

int main() {
	int t, i, lower, upper, t_;
	long long d, d_;

	scanf("%d%d", &n, &t);
	for (i = 0; i < n; i++)
		scanf("%d%d%d%d", &xx[i], &yy[i], &ddx[i], &ddy[i]);
	lower = -1, upper = t + 1, t_ = -1, d_ = INF;
	while (upper - lower > 1) {
		t = (lower + upper) / 2;
		for (i = 0; i < n; i++) {
			xx_[i] = xx[i] + ddx[i] * t;
			yy_[i] = yy[i] + ddy[i] * t;
		}
		d = solve();
		if (d_ > d || d_ == d && t_ > t)
			d_ = d, t_ = t;
		if (dot2(xx_[j_] - xx_[i_], yy_[j_] - yy_[i_], ddx[j_] - ddx[i_], ddy[j_] - ddy[i_]) >= 0)
			upper = t;
		else
			lower = t;
	}
	printf("%d\n", t_);
	printf("%lld\n", d_);
	return 0;
}

Compilation message (stderr)

dist.c: In function 'solve':
dist.c:73:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   73 |   if (o == -1 || xx_[o] > xx_[i] || xx_[o] == xx_[i] && yy_[o] > yy_[i])
      |                                     ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
dist.c: In function 'main':
dist.c:115:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  115 |   if (d_ > d || d_ == d && t_ > t)
      |                 ~~~~~~~~^~~~~~~~~
dist.c:104:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%d%d", &n, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
dist.c:106:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%d%d%d%d", &xx[i], &yy[i], &ddx[i], &ddy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 40 / 40
• Subtask 3: 39 / 39
• Subtask 4: 19 / 19