首页 > 代码库 > CSU 1503: 点到圆弧的距离(计算几何)
CSU 1503: 点到圆弧的距离(计算几何)
题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1503
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 -1
3 4 0 5 -3 4 0 1
Sample Output
Case 1: 1.414
Case 2: 4.000
HINT
Source
湖南省第十届大学生计算机程序设计竞赛
PS:
分两种情况:
第一种:点跟圆心的连线在那段扇形的圆弧范围内,点到圆弧的最短距离为点到圆心的距离减去半径然后取绝对值;
第二种:点跟圆心的连线不在那段扇形的圆弧范围内,点到圆弧的最短的距离为到这段圆弧的两个端点的最小值。
代码如下:(参考夏笑声)
#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\n",++cas,ans); } return 0; }
CSU 1503: 点到圆弧的距离(计算几何)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。