CSU 1503:点から円弧までの距離(計算ジオメトリ)

タイトルリンク:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1503
Description
点Pと円弧(円周の一部)を入力し、Pから円弧までの最短距離を計算します.言い換えれば、円弧上に点を探す必要があります.P点までの距離は最小です.ヒント:できるだけ正確なアルゴリズムを使用してください.それに比べて,近似アルゴリズムは本題のデータを通過することが困難である.
Input
最大10,000セットのデータを入力します.各データセットは、8個の整数x 1,y 1,x 2,y 2,x 3,y 3,xp,ypを含む.円弧の始点はA(x 1,y 1),通過点B(x 2,y 2),終了位置はC(x 3,y 3)である.点Pの位置は(xp,yp)である.入力保証A,B,Cはそれぞれ異なり、共線しない.上記のすべての点の座標絶対値は20を超えない.
Output
各セットのデータについて、テストポイント番号とPから円弧までの距離を出力し、3桁の小数を保持します.あなたの出力と標準出力の間には最大0.001の誤差があります.
Sample Input

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

Sample Output

Case 1: 1.414
Case 2: 4.000

HINT
Source
湖南省第10回大学生コンピュータプログラム設計コンテスト
PS:
2つのケースに分けられます.
第1種:点と円心の連線はその扇形の円弧の範囲内で、点から円弧までの最短距離は点から円心までの距離から半径を減算して絶対値をとる.
2つ目は、点と円心の連線が扇形の円弧の範囲内ではなく、点から円弧までの最短距離がこの円弧の2つの端点までの最小値である.
コードは以下の通りです(夏笑参照)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const double PI = acos(-1.0);

struct Point
{
    double x,y;
    friend Point operator - (Point a,Point b) //       
    {
        Point temp;
        temp.x = a.x - b.x;
        temp.y = a.y - b.y;
        return temp;
    }
};

Point p1, p2, p3, pc, pp;
double r;

Point get_pc1(Point p1, Point p2, Point p3)  //   
{
    double a, b, c, d, e, f;
    Point p;
    a = 2*(p2.x-p1.x);
    b = 2*(p2.y-p1.y);
    c = p2.x*p2.x+p2.y*p2.y-p1.x*p1.x-p1.y*p1.y;
    d = 2*(p3.x-p2.x);
    e = 2*(p3.y-p2.y);
    f = p3.x*p3.x+p3.y*p3.y-p2.x*p2.x-p2.y*p2.y;
    p.x = (b*f-e*c)/(b*d-e*a);
    p.y = (d*c-a*f)/(b*d-e*a);
    r = sqrt((p.x-p1.x)*(p.x-p1.x)+(p.y-p1.y)*(p.y-p1.y));//  
    return p;
}
double dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double mult_cha(Point p1,Point p2)   //  
{
    return p1.x * p2.y - p2.x * p1.y;
}

double get_ans(Point pc,Point pp,Point p1,Point p2,Point p3)
{
    double temp = mult_cha(p2-p1,p3-p1);//               
    double f1 = atan2((p1-pc).y,(p1-pc).x);// x      
    double f2 = atan2((p2-pc).y,(p2-pc).x);
    double f3 = atan2((p3-pc).y,(p3-pc).x);
    double f4 = atan2((pp-pc).y,(pp-pc).x);

    double ans1 = fabs(dis(pp,pc) - r);//       
    double ans2 = min(dis(pp,p1),dis(pp,p3));//        

    if(temp < 0)    //     
    {
        if(f1 < f3) //      ，   
        {
            if((f2 >= f1 && f2 <= f3) == (f4 >= f1 && f4 <= f3) )//p  p2       
                return ans1;
            else                        //p  p2        
                return ans2;
        }
        else//   
        {
            if((f2 >= f3 && f2 <= f1) == (f4 >=f3 && f4 <= f1) )
                return ans1;
            else
                return ans2;
        }
    }
    else
    {
        if(f1 > f3)
        {
            if((f2 <= f1 && f2 >= f3) == (f4 <= f1 && f4 >= f3) )
                return ans1;
            else
                return ans2;
        }
        else
        {
            if((f2 <= f3 && f2 >= f1) == (f4 <= f3 && f4 >= f1) )
                return ans1;
            else
                return ans2;
        }
    }
}

int main()
{
    int cas = 0;
    while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y,&p3.x,&p3.y,&pp.x,&pp.y))
    {
        pc = get_pc1(p1,p2,p3);//  
        double ans = get_ans(pc,pp,p1,p2,p3);

        printf("Case %d: %.3lf
",++cas,ans);
    }
    return 0;
}