1065: 点到圆弧的距离

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Special Judger Creator：
Submit：15 Solved：6

Description

输入一个点P和一条圆弧（圆周的一部分），你的任务是计算P到圆弧的最短距离。换句话说，你需要在圆弧上找一个点，到P点的距离最小。
提示：请尽量使用精确算法。相比之下，近似算法更难通过本题的数据。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

输入包含最多10000组数据。每组数据包含8个整数x1, y1, x2, y2, x3, y3, xp, yp。圆弧的起点是A(x1,y1)，经过点B(x2,y2)，结束位置是C(x3,y3)。点P的位置是 (xp,yp)。输入保证A, B, C各不相同且不会共线。上述所有点的坐标绝对值不超过20。

Output

对于每组数据，输出测试点编号和P到圆弧的距离，保留三位小数。你的输出和标准输出之间最多能有0.001的误差。

Sample Input Copy 

0 0 1 1 2 0 1 -1
3 4 0 5 -3 4 0 1

Sample Output Copy 

Case 1: 1.414
Case 2: 4.000

HINT

三角形外接圆，圆心坐标：

Point waixin(Point a,Point b,Point c) ///外接圆圆心坐标

 {
     Point p;
     double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1*a1 + b1*b1)/2;
     double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2*a2 + b2*b2)/2;
     double d = a1*b2 - a2*b1;
     p.x = a.x + (c1*b2 - c2*b1)/d, p.y=a.y + (a1*c2 -a2*c1)/d;
     return p;
 }

Source/Category