首页 > 代码库 > CSU 1503 点到圆弧的距离（2014湖南省程序设计竞赛A题）
CSU 1503 点到圆弧的距离（2014湖南省程序设计竞赛A题）
题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1503
解题报告：分两种情况就可以了，第一种是那个点跟圆心的连线在那段扇形的圆弧范围内，这样的话点到圆弧的最短距离就是点到圆心的距离减去半径然后再取绝对值就可以了，第二种情况是那个点跟圆心的连线不在那段扇形的圆弧范围内，这样的话，最短的距离就是到这段圆弧的端点的最小值。
接下来的第一步就是求圆心的坐标跟圆的半径，只要求出圆心坐标半径就好说了，求圆心坐标我用的方法是：
设圆心坐标是(a,b)，然后列方程：
(x1-a)^2 + (y1-b)^2 = r^2;
(x2-a)^2 + (y2-b)^2 = r^2;
(x3-a)^2 + (y3-b)^2 = r^2;
然后这样的话，计算过程中会出现y2-y1做分母的情况，所以，我又分了两种情况来讨论。
求出圆心坐标然后接下来的问题就只有怎么判断那个点跟圆心的连线是不是在扇形的圆弧范围内了，我也是用了分情况讨论的，但这里分的情况还是比较多的，一开始分了8种情况，然后压缩了一下，变成4种情况，分别是：
判断给点的顺序是顺时针还是逆时针，然后判断区间的方向，然后就是判断那个点是不是跟p2点在同一个区间就可以了。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const double eps = 1e-6,PI = acos(-1.0); 8 9 struct Point 10 { 11 double x,y; 12 friend Point operator - (Point a,Point b) 13 { 14 Point temp; 15 temp.x = a.x - b.x; 16 temp.y = a.y - b.y; 17 return temp; 18 } 19 }; 20 21 Point p1,p2,p3,pc,pp; 22 double r; 23 24 Point get_pc1(Point p1, Point p2, Point p3) //求圆心 25 { 26 Point p; 27 if(fabs(p1.y-p2.y) > eps) //因为计算过程中有出现(y2-y1)做分母的情况，所以这里分了两种情况讨论 28 { 29 // double t1 = p3.x*p3.x - p1.x*p1.x+p3.y*p3.y-p1.y*p1.y-((p3.y-p1.y)*(p1.x*p1.x-p2.x*p2.x+p1.y*p1.y-p2.y*p2.y)) / (p2.y-p1.y); 30 // double t2 = 2.0*(p3.x-p1.x)-(2*(p3.y-p1.y)*(p2.x-p1.x)) / (p2.y-p1.y); 31 double t1 = (p2.x*p2.x-p1.x*p1.x+p2.y*p2.y-p1.y*p1.y) *(p3.y-p1.y) - (p2.y-p1.y)*(p3.x*p3.x-p1.x*p1.x+p3.y*p3.y-p1.y*p1.y); 32 double t2 = 2.0*((p3.y-p1.y)*(p2.x-p1.x) - (p2.y-p1.y)*(p3.x-p1.x)); 33 p.x = t1 / t2; 34 p.y = (p2.x*p2.x-p1.x*p1.x+p2.y*p2.y-p1.y*p1.y-2*(p2.x-p1.x)*p.x) / (2*(p2.y-p1.y)); 35 } 36 else 37 { 38 p.x = (p2.x*p2.x-p1.x*p1.x+p2.y*p2.y-p1.y*p1.y) / (2*(p2.x-p1.x)); 39 p.y = (p3.x*p3.x-p1.x*p1.x+p3.y*p3.y-p1.y*p1.y-2*(p3.x-p1.x)*p.x) / (2*(p3.y-p1.y)); 40 } 41 return p; 42 } 43 double dis(Point a,Point b) 44 { 45 return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); 46 } 47 double mult_ca(Point p1,Point p2) //叉乘 48 { 49 return p1.x * p2.y - p2.x * p1.y; 50 } 51 52 double get_ans(Point pc,Point pp,Point p1,Point p2,Point p3) 53 { 54 double temp = mult_ca(p2-p1,p3-p1); 55 double f1 = atan2((p1-pc).x,(p1-pc).y); 56 double f2 = atan2((p3-pc).x,(p3-pc).y); 57 double f3 = atan2((p2-pc).x,(p2-pc).y); 58 double f4 = atan2((pp-pc).x,(pp-pc).y); 59 double ans1 = fabs(dis(pp,pc)-dis(p1,pc)); 60 double ans2 = min(dis(pp,p1),dis(pp,p3)); 61 if(temp < 0) //顺时针给点 62 { 63 if(f1 < f2) //判断区间方向，这样有利于判断p点和p2点是不是在同一个区间 64 { 65 if((f3 >= f1 && f3 <= f2) == (f4 >= f1 && f4 <= f2) ) return ans1; 66 else return ans2; 67 } 68 else 69 { 70 if((f3 >= f2 && f3 <= f1) == (f4 >=f2 && f4 <= f1) ) return ans1; 71 else return ans2; 72 } 73 } 74 else 75 { 76 if(f2 < f1) 77 { 78 if((f3 >= f2 && f3 <= f1) == (f4 >= f2 && f4 <= f1) ) return ans1; 79 else return ans2; 80 } 81 else 82 { 83 if((f3 >= f1 && f3 <= f2) == (f4 >= f1 && f4 <= f2)) return ans1; 84 else return ans2; 85 } 86 } 87 } 88 89 int main() 90 { 91 // freopen("in","r",stdin); 92 int kase = 1; 93 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)!=EOF) 94 { 95 pc = get_pc1(p1,p2,p3); 96 double ans = get_ans(pc,pp,p1,p2,p3); 97 printf("Case %d: %.3lf\n",kase++,ans); 98 } 99 return 0;100 }
CSU 1503 点到圆弧的距离（2014湖南省程序设计竞赛A题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。