[LightOJ1240]Point Segment Distance 题解

题意简述

原题LightOJ 1240，Point Segment Distance(3D)。

求三维空间里线段AB与C。

题解

我们设一个点在线段AB上移动，然后发现这个点与原来的C点的距离呈一个单峰状，于是珂以三分。

三分的时候处理一下，把A点坐标移动到(0,0,0)珂以方便操作。

代码

#include <cstdio>

#include <cmath> 

namespace fast_IO{

    const int IN_LEN = 10000000, OUT_LEN = 10000000;

    char ibuf[IN_LEN], obuf[OUT_LEN], *ih = ibuf + IN_LEN, *oh = obuf, *lastin = ibuf + IN_LEN, *lastout = obuf + OUT_LEN - 1;

    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, 1, IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}

    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, 1, oh - obuf, stdout), oh = obuf; *oh ++= x;}

    inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}

    int read(){

        int x = 0; int zf = 1; char ch = ' ';

        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar_();

        if (ch == '-') zf = -1, ch = getchar_();

        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar_(); return x * zf;

    }

    void write(int x){

        if (x < 0) putchar_('-'), x = -x;

        if (x > 9) write(x / 10);

        putchar_(x % 10 + '0');

    }

}

using namespace fast_IO;

struct Pos{

	double x, y, z;

} pos[3];

long double cacDis(Pos &a, Pos &b){

	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));

}

long double cac(long double num){

	Pos _new = (Pos){pos[1].x * num, pos[1].y * num, pos[1].z * num};

	Pos mid = (Pos){(_new.x + pos[0].x) / 2, (_new.y + pos[0].y) / 2, (_new.z + pos[0].z) / 2};

	return cacDis(mid, pos[2]);

}

int main(){

	int t = read();

	for (int j = 1; j <= t; ++j){

		pos[0].x = read(), pos[0].y = read(), pos[0].z = read();

		pos[1].x = read(), pos[1].y = read(), pos[1].z = read(	);

		pos[1].x -= pos[0].x, pos[1].y -= pos[0].y, pos[1].z -= pos[0].z;

		pos[2].x = read(), pos[2].y = read(), pos[2].z = read();

		pos[2].x -= pos[0].x, pos[2].y -= pos[0].y, pos[2].z -= pos[0].z;

		pos[0].x -= pos[0].x, pos[0].y -= pos[0].y, pos[0].z -= pos[0].z;

		long double l = 0, r = 2.0, mid;

		long double mmid; long double ans = 0.0;

		for (int i = 1; i <= 100; ++i){

			mid = (l + r) / 2;

			mmid = (mid + r) / 2;

			if (cac(mid) <= cac(mmid))

				r = mmid, ans = mmid;

			else

				l = mid;

		}

		printf("Case %d: %.9Lf\n", j, cac(ans));

	}

	return 0;

}

巴特西

[LightOJ1240]Point Segment Distance 题解

题意简述

题解

代码

最新文章

热门文章