1503: 点到圆弧的距离

Time Limit: 1 Sec  Memory Limit: 128 MB  Special Judge

Submit: 325  Solved: 70

[][][]

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

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

Sample Output

Case 1: 1.414Case 2: 4.000

HINT

 

Source

 

思路：根据三点确定圆心和半径；关键是确定扇形区域（尤其是优弧）

 

 

 

 

确定点在扇形区域就分两种情况，在圆内和圆外；不在扇形区域就是min(到A，到C)距离最短的；

 

 

转载请注明出处：  

 

题目链接： #

 

具体见代码：

 

1 #include
      
         2 #include
       
          3 #define PI acos(-1.0)  4 #include
        
           5 using namespace std;  6 struct Point  7 {  8     double x;  9     double y; 10     Point(double x=0,double y=0):x(x),y(y) {} //构造函数，方便代码编写 11 } pt; 12 struct Traingle 13 { 14     struct Point p[3]; 15 } Tr; 16 struct Circle 17 { 18     struct Point center; 19     double r; 20 } ans; 21 //计算两点距离 22 double Dis(struct Point p, struct Point q) 23 { 24     double dx=p.x-q.x; 25     double dy=p.y-q.y; 26     return sqrt(dx*dx+dy*dy); 27 } 28 //计算三角形面积 29 double Area(struct Traingle ct) 30 { 31     return fabs((ct.p[1].x-ct.p[0].x)*(ct.p[2].y-ct.p[0].y)-(ct.p[2].x-ct.p[0].x)*(ct.p[1].y-ct.p[0].y))/2.0; 32 } 33 //求三角形的外接圆，返回圆心和半径(存在结构体"圆"中) 34 struct Circle CircumCircle(struct Traingle t) 35 { 36     struct Circle tmp; 37     double a, b, c, c1, c2; 38     double xA, yA, xB, yB, xC, yC; 39     a = Dis(t.p[0], t.p[1]); 40     b = Dis(t.p[1], t.p[2]); 41     c = Dis(t.p[2], t.p[0]); 42 //根据 S = a * b * c / R / 4;求半径 R 43     tmp.r = (a*b*c)/(Area(t)*4.0); 44     xA = t.p[0].x; 45     yA = t.p[0].y; 46     xB = t.p[1].x; 47     yB = t.p[1].y; 48     xC = t.p[2].x; 49     yC = t.p[2].y; 50     c1 = (xA*xA+yA*yA - xB*xB-yB*yB) / 2; 51     c2 = (xA*xA+yA*yA - xC*xC-yC*yC) / 2; 52     tmp.center.x = (c1*(yA - yC)-c2*(yA - yB)) / ((xA - xB)*(yA - yC)-(xA - xC)*(yA - yB)); 53     tmp.center.y = (c1*(xA - xC)-c2*(xA - xB)) / ((yA - yB)*(xA - xC)-(yA - yC)*(xA - xB)); 54     return tmp; 55 } 56  57 typedef Point Vector; 58  59  60 Vector operator + (Vector A,Vector B) 61 { 62     return Vector(A.x+B.x,A.y+B.y); 63 } 64  65  66 Vector operator - (Point A,Point B) 67 { 68     return Vector(A.x-B.x,A.y-B.y); 69 } 70  71  72 Vector operator * (Vector A,double p) 73 { 74     return Vector(A.x*p,A.y*p); 75 } 76  77  78 Vector operator / (Vector A,double p) 79 { 80     return Vector(A.x/p,A.y/p); 81 } 82  83  84 bool operator < (const Point& a,const Point& b) 85 { 86     return a.x
         
          =0&&Cross(OB,OC)<0&&Cross(OA,OC)>0||Cross(OA,OB)<0&&Cross(OB,OC)>=0&&Cross(OA,OC)>0)//顺138         {139             if(Cross(OA,OD)<=0&&Cross(OD,OC)<=0||Cross(OA,OD)>=0&&Cross(OD,OC)<0&&Cross(OA,OC)>0||Cross(OA,OD)<0&&Cross(OD,OC)>=0&&Cross(OA,OC)>0)140             {141                 len=fabs(length(D-O));142                 if(len<=CC.r) len=CC.r-len;143                 else len=len-CC.r;144             }145             else146             {147                 len=min(fabs(length(A-D)),fabs(length(C-D)));148             }149         }150         else if(Cross(OA,OB)>=0&&Cross(OB,OC)>=0||Cross(OA,OB)>0&&Cross(OB,OC)<=0&&Cross(OA,OC)<0||Cross(OA,OB)<=0&&Cross(OB,OC)>0&&Cross(OA,OC)<0)//逆151         {152             if(Cross(OA,OD)>=0&&Cross(OD,OC)>=0||Cross(OA,OD)>0&&Cross(OD,OC)<=0&&Cross(OA,OC)<0||Cross(OA,OD)<=0&&Cross(OD,OC)>0&&Cross(OA,OC)<0)153             {154                 len=fabs(length(D-O));155                 if(len<=CC.r) len=CC.r-len;156                 else len=len-CC.r;157             }158             else159             {160                 len=min(fabs(length(A-D)),fabs(length(C-D)));161             }162         }163 164         printf("Case %d: %0.3f\n",ca++,len);165     }166     return 0;167 }168 /*169 0 0 1 1 2 0 1 -1170 3 4 0 5 -3 4 0 1171 0 0 1 1 1 -1 0 -1172 */