NC204857. 最短路
描述
输入描述
第一行四个整数
，
表示牛能家的坐标，
表示牛可乐家的坐标。
第二行三个整数
，
表示被诅咒的圆形区域的位置的圆心坐标，
表示这个圆形区域的半径。
输出描述
在一行中输出牛能从家到牛可乐家的最短路。
示例1
输入:
-1 -1 1 1 0 0 1
输出:
3.570796
示例2
输入:
1 1 2 2 0 0 1
输出:
1.414214
C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 488K, 提交时间: 2020-06-16 19:58:40
#include<stdio.h>
#include<math.h>
using namespace std;
struct p
{
double x,y;
} a,b,c;
double dis(p a,p b)
{
return hypot(a.x-b.x,a.y-b.y);
}
int main()
{
double r;
scanf("%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&r);
double d1=dis(a,b),d2=dis(a,c),d3=dis(b,c);
double g1=acos((d2*d2+d3*d3-d1*d1)/(2*d2*d3)),g2=acos(r/d2),g3=acos(r/d3);
if(g2+g3>g1)
printf("%.6lf\n",d1);
else
printf("%.6lf\n",sqrt(d2*d2-r*r)+sqrt(d3*d3-r*r)+(g1-g2-g3)*r);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 608K, 提交时间: 2020-04-23 08:57:36
#include<bits/stdc++.h>
using namespace std;
struct p{
double x,y;
}a,b,c;
double dis(p a,p b){
return hypot(a.x-b.x,a.y-b.y);
}
int main(){
double r;
scanf("%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&r);
double d1=dis(a,b),d2=dis(a,c),d3=dis(b,c);
double g1=acos((d2*d2+d3*d3-d1*d1)/(2*d2*d3)),g2=acos(r/d2),g3=acos(r/d3);
if(g2+g3>g1) printf("%.6lf\n",d1);
else printf("%.6lf\n",sqrt(d2*d2-r*r)+sqrt(d3*d3-r*r)+(g1-g2-g3)*r);
return 0;
}