点到圆弧的距离_到弧的距离_KM6714的博客-程序员秘密

技术标签：几何

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

<span class="sampledata" style="font-family: monospace; font-size: 18px; white-space: pre; background-color: rgb(141, 184, 255);">0 0 1 1 2 0 1 -1
3 4 0 5 -3 4 0 1</span>

Sample Output

<span class="sampledata" style="font-family: monospace; font-size: 18px; white-space: pre; background-color: rgb(141, 184, 255);">Case 1: 1.414
Case 2: 4.000</span>

HINT

Source

湖南省第十届大学生计算机程序设计竞赛

PS：

分两种情况：

第一种：点跟圆心的连线在那段扇形的圆弧范围内，点到圆弧的最短距离为点到圆心的距离减去半径然后取绝对值；

第二种：点跟圆心的连线不在那段扇形的圆弧范围内，点到圆弧的最短的距离为到这段圆弧的两个端点的最小值。

代码如下：（参考夏笑声）

[cpp]view plaincopy
print?
 #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;  
 }  

本文链接：https://blog.csdn.net/T_ravelers/article/details/51312639

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

第14课：郭盛华课程_VB编程之如何操作文件_郭盛华的博客-程序员秘密

主讲老师：郭盛华文件操作：在一个应用程序中，对文件的处理是一个比较常用的操作，如打开文件、保存文件，等等。Visual Basic 提供了三个控件对磁盘文件夹与文件进行显示与操作，它们分别是：DriveListBox（磁盘列表框）控件、DirListBox（文件夹列表框）控件，以及 FileListBox（文件列表框）控件。如图一：一、DriveListBo...

NYU AI作业习题-活动安排问题 BFS+DFS Iterative deepening depth-first search_LarryNLPIR的博客-程序员秘密

题目链接 http://cs.nyu.edu/courses/spring12/CSCI-GA.2560-001/prog1.html题目大意：给定n个任务的时间、价值及先后序关系，求一个可行的任务子集，使得时间之和不大于deadline，价值之和不小于targetVaule，且不可出现逆序。算法思路：题目已经给出算法，转化为状态空间搜索问题（tree-structured state

[读史思考]为何此大神可以同时进入文庙和武庙？_罗西的思考的博客-程序员秘密

带着孩子学历史，突然发现一个神人：杜预。为何神奇？因为杜预是明朝之前唯一一个同时进入文庙和武庙的历史人物。于是查找资料，想知道他为何可以同时入选，遂有此文章和大家共享，文末有专门针对程序员的借鉴之处。

Navicat for MySQL 1130 - Host 'DeskTop-**' is not allowed to connect to this MySQL-server_一博是我的的博客-程序员秘密

GRANT ALL PRIVILEGES ON *.* TO 'root'@'%' INDENTIFIED BY 'abc' WITH GRANT OPTION;意思是所有用户名为root，密码为abc的用户都可以连接navicat接下来刷新权限flush privileges;即可连接成功...

《征信业务管理办法》发布_M13601260375的博客-程序员秘密

为贯彻落实党中央、国务院关于征信业规范发展的决策部署，推进征信法治建设，践行“征信为民”理念，加强个人信息保护，中国人民银行发布《征信业务管理办法》，自2022年1月1日起施行。《征信业务管理办法》是《征信业管理条例》的配套制度，与《征信机构管理办法》共同构成征信法治体系的重要组成部分，对依法从严加强征信监管，保障信息主体合法权益和信息安全，促进征信业市场化、法治化和科技化发展具有积极意义。《征信业管理条例》实施以来，中国人民银行推动国家金融信用信息基础数据库不断完善服务功能，取得突破性进展，在防范金融

JMeter 动态参数请求_jmeter请求参数怎么动态_SilenceXSJ的博客-程序员秘密

JMeter 动态参数请求添加执行任务设置全局参数设置cookice添加http请求可设置请求头信息请求方式数据传输方式等使用 BeanShell PreProcessor 前置处理参数可添加察看结果树或者图形结果等观察JMeter 动态参数请求添加执行任务设置全局参数设置tonken data 等自定义变量设置cookice如果要测试要登陆的网站 , 可以先