点到圆弧的距离_点到圆弧的最短距离-程序员宅基地

技术标签: 几何  

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 plain   copy
  print ? 在CODE上查看代码片 派生到我的代码片
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <cmath>  
  4. #include <iostream>  
  5. #include <algorithm>  
  6. using namespace std;  
  7. const double 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.     double a, b, c, d, e, f;  
  27.     Point p;  
  28.     a = 2*(p2.x-p1.x);  
  29.     b = 2*(p2.y-p1.y);  
  30.     c = p2.x*p2.x+p2.y*p2.y-p1.x*p1.x-p1.y*p1.y;  
  31.     d = 2*(p3.x-p2.x);  
  32.     e = 2*(p3.y-p2.y);  
  33.     f = p3.x*p3.x+p3.y*p3.y-p2.x*p2.x-p2.y*p2.y;  
  34.     p.x = (b*f-e*c)/(b*d-e*a);  
  35.     p.y = (d*c-a*f)/(b*d-e*a);  
  36.     r = sqrt((p.x-p1.x)*(p.x-p1.x)+(p.y-p1.y)*(p.y-p1.y));//半径  
  37.     return p;  
  38. }  
  39. double dis(Point a,Point b)  
  40. {  
  41.     return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));  
  42. }  
  43. double mult_cha(Point p1,Point p2)   //叉积  
  44. {  
  45.     return p1.x * p2.y - p2.x * p1.y;  
  46. }  
  47.   
  48. double get_ans(Point pc,Point pp,Point p1,Point p2,Point p3)  
  49. {  
  50.     double temp = mult_cha(p2-p1,p3-p1);//判断给点方向是顺时针还是逆时针  
  51.     double f1 = atan2((p1-pc).y,(p1-pc).x);//和x正半轴的夹角  
  52.     double f2 = atan2((p2-pc).y,(p2-pc).x);  
  53.     double f3 = atan2((p3-pc).y,(p3-pc).x);  
  54.     double f4 = atan2((pp-pc).y,(pp-pc).x);  
  55.   
  56.     double ans1 = fabs(dis(pp,pc) - r);//到圆心减去半径  
  57.     double ans2 = min(dis(pp,p1),dis(pp,p3));//取到端点的较小值  
  58.   
  59.     if(temp < 0)    //顺时针给点  
  60.     {  
  61.         if(f1 < f3) //判断区间方向,向下凹  
  62.         {  
  63.             if((f2 >= f1 && f2 <= f3) == (f4 >= f1 && f4 <= f3) )//p点和p2点在同一个区间  
  64.                 return ans1;  
  65.             else                        //p点和p2点不在同一个区间  
  66.                 return ans2;  
  67.         }  
  68.         else//向上凸  
  69.         {  
  70.             if((f2 >= f3 && f2 <= f1) == (f4 >=f3 && f4 <= f1) )  
  71.                 return ans1;  
  72.             else  
  73.                 return ans2;  
  74.         }  
  75.     }  
  76.     else  
  77.     {  
  78.         if(f1 > f3)  
  79.         {  
  80.             if((f2 <= f1 && f2 >= f3) == (f4 <= f1 && f4 >= f3) )  
  81.                 return ans1;  
  82.             else  
  83.                 return ans2;  
  84.         }  
  85.         else  
  86.         {  
  87.             if((f2 <= f3 && f2 >= f1) == (f4 <= f3 && f4 >= f1) )  
  88.                 return ans1;  
  89.             else  
  90.                 return ans2;  
  91.         }  
  92.     }  
  93. }  
  94.   
  95. int main()  
  96. {  
  97.     int cas = 0;  
  98.     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))  
  99.     {  
  100.         pc = get_pc1(p1,p2,p3);//圆心  
  101.         double ans = get_ans(pc,pp,p1,p2,p3);  
  102.   
  103.         printf("Case %d: %.3lf\n",++cas,ans);  
  104.     }  
  105.     return 0;  
  106. }  
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/T_ravelers/article/details/51312639

智能推荐

MobaXterm详细使用教程_mobaxterm_personal-程序员宅基地

文章浏览阅读10w+次,点赞292次,收藏2.3k次。这一篇MobaXterm详细使用教程,我们来介绍一下如何设置并用MobaXterm来连接Linux服务器。MobaXterm 又名 MobaXVT,是一款增强型终端、X 服务器和 Unix 命令集(GNU/ Cygwin)工具箱。MobaXterm 可以开启多个终端视窗,以最新的 X 服务器为基础的X.Org,可以轻松地来试用 Unix/Linux 上的 GNU Unix 命令。这样一来,我们可以不用安装虚拟机来试用虚拟环境,然后只要通过 MobaXterm 就可以使用大多数的 linux 命令。._mobaxterm_personal

PTA甲级 1013 Battle Over Cities (25分) BFS,DFS,查并集_pta甲级1013第二个检查点-程序员宅基地

文章浏览阅读151次。强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬本文由参考于柳神博客写成柳神的程序员宅基地,这个可以搜索文章柳神的个人博客,这个没有广告,但是不能搜索还有就是非常非常有用的 算法笔记 全名是算法笔记 上级训练实战指南 //这本都是PTA的题解算法笔记PS 今天也要加油鸭题目原文It is vitally important to have all the cities connected by highways in a war. If a city is occupied _pta甲级1013第二个检查点

一个WP8样式的Android ProgressBar_android wp样式-程序员宅基地

文章浏览阅读1.1k次。一个WP8样式的进度对话框_android wp样式

NOI2018T1 归程_noi2018-t1-程序员宅基地

文章浏览阅读563次。  原题传送门 luoguP4768 NOI2018T1 归程题目大意  本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 nnn 个节点、mmm 条边的无向连通图(节点的编号从 111 至 nnn)。我们依次用 l,al,al,a 描述一条边的长度、海拔。  作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位_noi2018-t1

C++Primer_课后习题第十二章_#include < iostream.h> #include < string.h> class -程序员宅基地

文章浏览阅读296次。本文答案,部分参考于C++ Primer 习题集前面章节的习题答案第一章第二章第三章第四章第五章第六章第七章第八章第九章第十章第十一章配套的学习资料https://www.jianguoyun.com/p/DTK5uJgQldv8CBjKv80D12.1都是4个StrBlob中的那个vector是共享的.12.2#pragma once#ifndef MY_STRBLOB_H#define MY_STRBLOB_H#include<vector>#i_#include < iostream.h> #include < string.h> class strtype { public: strtype(

创建user01-user20 随机六位数密码 a-z A-Z 0-9_sg85,cc-程序员宅基地

文章浏览阅读752次。一:创建的要求1)创建user01-user022)生成20组随机密码3)设置密码4)输出清单二:代码及测试结果adduser () {pw_txt=`mktemp pw.XXXXX`#1)创建用户for i in `seq -s ' ' -w 1 20` #-s表示横着输出,-w表示保持宽度,即把1 2 3 变成01 02 03这样do useradd user$idone#2)生成随机密码cat /dev/urandom | strings -6 |e_sg85,cc

随便推点

scala中的特质_scala success特质-程序员宅基地

文章浏览阅读2k次。scala中的特质1.特质中定义的方法可以实现,【有了大括号的就是已经实现过的方法,例如下面Animal中的listen和run】;也可以不实现【例如Animal类中的speak方法】示例代码如下:package cookBook.chapter8trait Animal{ //没有实现 def speak def listen: Unit ={ } ..._scala success特质

SQL语句练习题目-程序员宅基地

文章浏览阅读875次。sql语句练习题目员工信息表 staff: user_id , name, store_id, salary商店表store:store_id, name,city题目1:找出平均工资小于5000的商店所在的城市SELECT a.ctity,AVG(b.salary) FROM store a,staff bWHERE a.store_id=b.store_idG...

HTML期末作业:基于html+css+javascript+jquery实现古诗词网页 学生网页设计作品 web前端开发技术 web课程设计 网页规划与设计-程序员宅基地

文章浏览阅读198次。 关于作者: 历任研发工程师,技术组长,教学总监;曾于2016年、2020年两度荣获CSDN年度十大博客之星。 十载寒冰,难凉热血;多年过去,历经变迁,物是人非。 然而,对于技术的探索和追求从未停歇。 坚持原创,热衷分享,初心未改,继往开来!茶文化网站、️‍中华传统文化题材、京剧文化水墨风书画、中国民间年画文化艺术网站 、等网站的设计与制作。️ 这个首页代码运用了DIV盒子的使用方法,如盒子的嵌套、浮动、margin、border、background等属性的使用,外部大盒

图像直方图均衡化和局部增强处理_基于直方图的局部增强-程序员宅基地

文章浏览阅读1.9w次,点赞15次,收藏123次。一、基本原理1.1直方图均衡化(一提高图像的对比度,二使像素值几乎成均匀分布的图像0表示黑,1表示白,中心思想是把原始图像的灰度直方图从比较集中的某个灰度区间变成在全部灰度范围内的均匀分布,增加许多图像的局部对比度,亮度可以更好的在直方图上分布。) 灰度级的直方图就是反映一幅图像中的灰度级与出现这种灰度的概率之间的关系的图形。设变量代表图像中的像素灰度级。在图像中,像素的灰度级可作归一化处理..._基于直方图的局部增强

echarts饼状图圆环位置修改样式调整_echarts环形图位置-程序员宅基地

文章浏览阅读5k次。作为笔记(echarts篇)pie图例组件:legend: { type: 'scroll',//图例数量过多时,可以使用滚动 left: 'center', bottom: this.ringData.legendBottom || 0,//设置位置 data: this.ringData.name, textStyle: { color: '#fff'//..._echarts环形图位置

机器学习-AdaBoost算法_adaboostclassifier()-程序员宅基地

文章浏览阅读600次。简介Adaboost算法是一种提升方法,将多个弱分类器,组合成强分类器。AdaBoost,是英文”Adaptive Boosting“(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于:前一个弱分类器分错的样本的权值(样本对应的权值)会得到加强,权值更新后的样本再次被用来训练下一个新的弱分类器。在每轮训练中,用总体(样本总体)训练新的弱分类器,产生新的样本权值、该弱分类器的话语权,一直迭代直到达到预定的错误率或达到指定的最大迭代次数。总体—_adaboostclassifier()

推荐文章

热门文章

相关标签