Easy Problem
Time limit:1000 ms Memory limit:65536 KB
Total Submit:1755 (462 users) Accepted Submit:366 (332 users)
Description
In this problem, you're to calculate the distance between a point
P(
xp,
yp,
zp) and a segment (
x1,
y1,
z1) − (
x2,
y2,
z2), in a 3D space, i.e. the minimal distance from P to any point
Q(
xq,
yq,
zq) on the segment (a segment is part of a line).
Input
The first line contains a single integer T (1 ≤
T ≤ 1000), the number of test cases. Each test case is a single line containing 9 integers
xp,
yp,
zp,
x1,
y1,
z1,
x2,
y2,
z2. These integers are all in [-1000,1000].
Output
For each test case, print the case number and the minimal distance, to two decimal places.
Sample Input
3
0 0 0 0 1 0 1 1 0
1 0 0 1 0 1 1 1 0
-1 -1 -1 0 1 0 -1 0 -1
Sample Output
Case 1: 1.00
Case 2: 0.71
Case 3: 1.00
Problem Source
The 32nd ACM-ICPC Beijing First Round Internet Contest
其實和二分差不多，劃個函數曲線出來，分三段，比劃一下就很容易理解了：）
#include <iostream>
#include <cmath>
using namespace std;
double dist(double l[], double r[]) 
{
return sqrt((l[0]-r[0])*(l[0]-r[0])+(l[1]-r[1])*(l[1]-r[1])+(l[2]-r[2])*(l[2]-r[2]));
}
int main() {
// freopen("1024.in", "r", stdin);
int n, cas=0;
double l[3], r[3], p[3], p1[3], p2[3], d1, d2;
scanf("%d", &n);
while (n--) {
scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf", &p[0], &p[1], &p[2], &l[0], &l[1], &l[2], &r[0], &r[1], &r[2]);
while (dist(l, r) > 1e-4) {
p1[0] = (l[0] + r[0]) / 2;
p1[1] = (l[1] + r[1]) / 2;
p1[2] = (l[2] + r[2]) / 2;
p2[0] = (r[0] + p1[0]) / 2;
p2[1] = (r[1] + p1[1]) / 2;
p2[2] = (r[2] + p1[2]) / 2;
d1 = dist(p1, p); d2 = dist(p2, p);
if (d2 >= d1) {
r[0] = p2[0]; r[1] = p2[1]; r[2] = p2[2];
} else {
l[0] = p1[0]; l[1] = p1[1]; l[2] = p1[2];
}
}
printf("Case %d: %.2lf\n", ++cas, dist(p,l));
}
}posted on 2007-10-18 11:00
豪 閱讀(1209)
評論(0) 編輯 收藏 引用 所屬分類:
算法&ACM