UVA 5788 Wally World

2024-08-23 03:32

文章标签 uva 5788 wally world

本文主要是介绍UVA 5788 Wally World，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

地址：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3799
Two star-crossed lovers want to meet. The two lovers are standing at distinct points in the plane (but then again, aren't we all?). They can travel freely except that there is a single wall which cannot be crossed. The wall is a line segment which is parallel to either the x or y axis. Each lover can move 1 unit in 1 second. How long will it take them to be together if they both choose the best path?
输入
Input for each test case will consist of two lines each containing four integers. The first two integers will specify the x and y coordinates of the first lover; the next two integers will specify the x and ycoordinates of the second lover. The next four integers will specify the start and end points of the wall. Furthermore, in all cases both lovers will not be on the (infinite) line containing the wall -- that is, the wall extended in both directions. All coordinates will be positive and less than or equal to 10000 and neither lover will start on the wall. The input will be terminated by a line containing four zeroes.
输出
For each test case, output the minimum time in seconds for the two lovers to meet. Print the answer to exactly 3 decimal places, using the output format shown in the example.、
输入
5 2 7 2
1 1 1 100
1 2 3 2
2 1 2 100
0 0 0 0
输出
Case 1: 1.000
Case 2: 1.414

题意： A为起点，B为终点。要求从A走到B不能直接通过线段CD的最短路程。
解题思路：
1、AB与CD不相交。ANS= AB
2、AB与CD相交。ANS=MIN(AC+BC,AD+BD)
代码：
#include <stdio.h>
#include <math.h>
struct point
{double x;double y;
};
double direction(point p1, point p2, point p)
{return (p1.x - p.x)*(p2.y - p.y) - (p2.x - p.x)*(p1.y - p.y);
}
int on_segment(point p1, point p2, point p)
{double max = p1.x > p2.x ? p1.x : p2.x;double min = p1.x < p2.x ? p1.x : p2.x;if (p.x >= min && p.x <= max)return 1;elsereturn 0;
}
//  判断线段p1p2是否与p3p4相交
int segments_intersert(point p1, point p2, point p3, point p4)
{double d1, d2, d3, d4;d1 = direction(p1, p2, p3);d2 = direction(p1, p2, p4);d3 = direction(p3, p4, p1);d4 = direction(p3, p4, p2);if (d1*d2 < 0 && d3*d4 < 0)return 1;else if (d1 == 0 && on_segment(p1, p2, p3))return 1;else if (d2 == 0 && on_segment(p1, p2, p4))return 1;else if (d3 == 0 && on_segment(p3, p4, p1))return 1;else if (d4 == 0 && on_segment(p3, p4, p2))return 1;return 0;
}
int main()
{point a, b, c, d;int C = 1;while (scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y) != EOF){double ans;if (a.x == 0 && a.y == 0 && b.x == 0 && b.y == 0)return 0;scanf("%lf%lf%lf%lf", &c.x, &c.y, &d.x, &d.y);if (segments_intersert(a, b, c, d)){double ac = sqrt((a.x - c.x)*(a.x - c.x) + (a.y - c.y)*(a.y - c.y));double bc = sqrt((b.x - c.x)*(b.x - c.x) + (b.y - c.y)*(b.y - c.y));double ad = sqrt((a.x - d.x)*(a.x - d.x) + (a.y - d.y)*(a.y - d.y));double bd = sqrt((b.x - d.x)*(b.x - d.x) + (b.y - d.y)*(b.y - d.y));ans = ac + bc;if (ans > (ad + bd))ans = ad + bd;}elseans = sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));printf("Case %d: %.3lf\n", C++, ans / 2.0);}return 0;
}