oj.uz

Submission #924822

# Submission time Handle Problem Language Result Execution time Memory
924822 2024-02-09T19:43:01 Z rainboy None (KOI16_dist) C
0 / 100
 2000 ms 1884 KB 
#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++) {
		while (h_ == h || 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

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:113:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  113 |   if (d_ > d || d_ == d && t_ > t)
      |                 ~~~~~~~~^~~~~~~~~
dist.c:102:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |  scanf("%d%d", &n, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
dist.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d%d%d%d", &xx[i], &yy[i], &ddx[i], &ddy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2095 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2095 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1884 KB Output is correct
2 Correct 31 ms 1624 KB Output is correct
3 Correct 36 ms 1628 KB Output is correct
4 Correct 32 ms 1628 KB Output is correct
5 Correct 34 ms 1828 KB Output is correct
6 Correct 25 ms 1560 KB Output is correct
7 Execution timed out 2021 ms 1624 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2095 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -