Submission #70391861

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <math.h>
#define EPS 1e-9
/* a * x**2 + b * x + c (a > 0) の st <= x <= et における最小値を求める */
long double getmin(long double a, long double b, long double c, long double st, long double et) {
#if 0
  long double kyokusyo_x = -b / (2.0 * a);
  long double x = kyokusyo_x;
  if (x < st) x = st;
  if (et < x) x = et;
  return a * x * x + b * x + c;
#else
  if (-b < st * 2.0 * a) {
    return a * st * st + b * st + c;
  } else if (et * 2.0 * a < -b) {
    return a * et * et + b * et + c;
  } else {
    /* return b * b / (4.0 * a) - b * b / (2.0 * a)+ c; */
    return -b * b / (4.0 * a) + c;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <math.h>

#define EPS 1e-9

/* a * x**2 + b * x + c (a > 0) の st <= x <= et における最小値を求める */
long double getmin(long double a, long double b, long double c, long double st, long double et) {
#if 0
	long double kyokusyo_x = -b / (2.0 * a);
	long double x = kyokusyo_x;
	if (x < st) x = st;
	if (et < x) x = et;
	return a * x * x + b * x + c;
#else
	if (-b < st * 2.0 * a) {
		return a * st * st + b * st + c;
	} else if (et * 2.0 * a < -b) {
		return a * et * et + b * et + c;
	} else {
		/* return b * b / (4.0 * a) - b * b / (2.0 * a)+ c; */
		return -b * b / (4.0 * a) + c;
	}
#endif
}

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		double TSX, TSY, TGX, TGY;
		double ASX, ASY, AGX, AGY;
		long double tdx, tdy, adx, ady, tvel, avel;
		long double midt, endt;
		long double a1, b1, c1, min1;
		long double a2, b2, c2, min2;
		long double min;
		if (scanf("%lf%lf%lf%lf", &TSX, &TSY, &TGX, &TGY) != 4) return 1;
		if (scanf("%lf%lf%lf%lf", &ASX, &ASY, &AGX, &AGY) != 4) return 1;
		tdx = TGX - TSX;
		tdy = TGY - TSY;
		tvel = sqrtl(tdx * tdx + tdy * tdy);
		tdx /= tvel;
		tdy /= tvel;
		adx = AGX - ASX;
		ady = AGY - ASY;
		avel = sqrtl(adx * adx + ady * ady);
		adx /= avel;
		ady /= avel;
		a1 = (tdx - adx) * (tdx - adx) + (tdy - ady) * (tdy - ady);
		b1 = 2.0 * ((TSX - ASX) * (tdx - adx) + (TSY - ASY) * (tdy - ady));
		c1 = (TSX - ASX) * (TSX - ASX) + (TSY - ASY) * (TSY - ASY);
		if (tvel <= avel) {
			midt = tvel;
			endt = avel;
			a2 = adx * adx + ady * ady;
			b2 = -2.0 * ((TGX - ASX) * adx + (TGY - ASY) * ady);
			c2 = (TGX - ASX) * (TGX - ASX) + (TGY - ASY) * (TGY - ASY);
		} else {
			midt = avel;
			endt = tvel;
			a2 = tdx * tdx + tdy * tdy;
			b2 = 2.0 * ((TSX - AGX) * tdx + (TSY - AGY) * tdy);
			c2 = (TSX - AGX) * (TSX - AGX) + (TSY - AGY) * (TSY - AGY);
		}
		if (fabs(a1) < EPS) {
			min1 = c1;
		} else {
			min1 = getmin(a1, b1, c1, 0, midt);
		}
		min2 = getmin(a2, b2, c2, midt, endt);
		min = min1 < min2 ? min1 : min2;
		printf("%.20f\n", (double)(min < 0 ? 0 : sqrtl(min)));
	}
	return 0;
}

/*

両方動いているとき

(x1, y1) = (TSX + tdx * t, TSY + tdy * t)
(x2, y2) = (ASX + adx * t, ASY + ady * t)

  (x1 - x2)**2 + (y1 - y2)**2
= ((TSX - ASX) + (tdx - adx) * t)**2 + ((TSY - ASY) + (tdy - ady) * t)**2
=   ((tdx - adx)**2 + (tdy - ady)**2) * t**2
  + 2 * ((TSX - ASX) * (tdx - adx) + (TSY - ASY) * (tdy - ady)) * t
  + (TSX - ASX)**2 + (TSY - ASY)**2

高橋君だけ動いているとき

(x1, y1) = (TSX + tdx * t, TSY + tdy * t)
(x2, y2) = (AGX, AGY)

  (x1 - x2)**2 + (y1 - y2)**2
= ((TSX - AGX) + tdx * t)**2 + ((TSY - AGY) + tdy * t)**2
=   (tdx**2 + tdy**2) * t**2
  + 2 * ((TSX - AGX) * tdx + (TSY - AGY) * tdy) * t
  + (TSX - AGX)**2 + ((TSY - AGY)**2

青木君だけ動いているとき

(x1, y1) = (TGX, TGY)
(x2, y2) = (ASX + adx * t, ASY + ady * t)

  (x1 - x2)**2 + (y1 - y2)**2
= ((TGX - ASX) - adx * t)**2 + ((TGY - ASY) - ady * t)**2
=   ((adx**2 + ady**2) * t**t
  - 2 * ((TGX - ASX) * adx + (TGY - ASY) * ady) * t
  + (TGX - ASX)**2 + (TGY - ASY)**2

*/

Submission Info

Judge Result