题目描述
输入一个点 P 和一条圆弧（圆周的一部分），你的任务是计算 P 到圆弧的最短距离。换句话 说，你需要在圆弧上找一个点，到 P点的距离最小。
提示：请尽量使用精确算法。相比之下，近似算法更难通过本题的数据。
提示：请尽量使用精确算法。相比之下，近似算法更难通过本题的数据。
输入
输入包含最多 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。
输出
对于每组数据，输出测试点编号和 P 到圆弧的距离，保留三位小数。
样例输入
0 0 1 1 2 0 1 -1
3 4 0 5 -3 4 0 1
样例输出
Case 1: 1.414
Case 2: 4.000
分两种情况：
第一种：点跟圆心的连线在那段扇形的圆弧范围内，点到圆弧的最短距离为点到圆心的距离减去半径然后取绝对值；
第二种：点跟圆心的连线不在那段扇形的圆弧范围内，点到圆弧的最短的距离为到这段圆弧的两个端点的最小值。
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-;
const double PI = acos(-1.0);
int casee = ;
int dcmp(double x) {
if(fabs(x) < eps) return ;
else return x < ? - : ;
}
struct Vector {
double x, y;
Vector(double x_ = , double y_ = ) : x(x_), y(y_) {} Vector operator+ (const Vector &a) const {
return Vector(x + a.x, y + a.y);
}
Vector operator- (const Vector &a) const {
return Vector(x - a.x, y - a.y);
}
Vector operator* (double p) {
return Vector(x * p, y * p);
}
friend Vector operator* (double p, const Vector &a) {
return Vector(a.x * p, a.y * p);
}
Vector operator/ (double p) {
return Vector(x / p, y / p);
}
bool operator== (const Vector &a) const {
return dcmp(x - a.x) == && dcmp(y - a.y) == ;
} friend double dmul(const Vector &a, const Vector &b) {
return a.x * b.x + a.y * b.y;
}
friend double cmul(const Vector &a, const Vector &b) {
return a.x * b.y - a.y * b.x;
}
friend double angle(const Vector &a, const Vector &b) {
return acos(dmul(a, b) / a.length() / b.length());
}
friend Vector rotate(const Vector &a, double rad) {
return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));
}
friend Vector normal(const Vector &a) {
double l = a.length();
return Vector(a.x / l, a.y / l);
} double length() const {
return sqrt(dmul(*this, *this));
}
};
typedef Vector Point;
double dis(Point A, Point B) {
return (A-B).length();
}
Point pp1, pp2, pp3, pp, o; Point get_cir(Point a,Point b,Point c) {//已知圆上3点,求圆的外心
double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/;
double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/;
double d=a1*b2-a2*b1;
return Point(a.x+(c1*b2-c2*b1)/d,a.y+(a1*c2-a2*c1)/d);
}
double AngleToX(Vector A, Vector B) {//向量与x轴正方向的夹角,范围[0,2*pi) B为(1,0)
double res = angle(A, B);
if(dcmp(cmul(A, B)) < ) res = PI * - res;
return res;
}
void gao (Point A,Point B,Point C,Point P,Point O)
{
Vector X(, );
Vector OA = A - O, OP = P - O, OC = C - O, OB = B - O;
double fa = AngleToX(OA, X);
double fb = AngleToX(OB, X);
double fc = AngleToX(OC, X);
double fp = AngleToX(OP, X);
double ans = min(dis(P, A), dis(P, C));
double r = dis(A, O);
if(fa>fc) swap(fa,fc);
if(dcmp(fa-fb)<= && dcmp(fb - fc) <= && dcmp(fa - fp) <= && dcmp(fp - fc) <= ) {
double r = dis(A, O);
ans = min(ans, fabs(dis(O, P) - r));
}
if(!(dcmp(fa - fb) <= &&dcmp(fb-fc)<= )&&!(dcmp(fa-fp)<=&&dcmp(fp-fc)<=)) {
ans = min(ans, fabs(dis(O, P)- r));
} printf("Case %d: %.3f\n", ++casee, ans);
}
int main() {
while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &pp1.x,&pp1.y,&pp2.x,&pp2.y,&pp3.x,&pp3.y,&pp.x,&pp.y)){
o=get_cir(pp1,pp2,pp3);
gao(pp1,pp2,pp3,pp,o);
}
return ;
}
解法2
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#define eps (1e-4)
#define N 205
#define dd double
#define sqr(x) ((x)*(x))
const double pi = acos(-);
using namespace std;
struct Point
{
double x,y;
};
double cross(Point a,Point b,Point c) ///叉积
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
double dis(Point a,Point b) ///距离
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
Point waixin(Point a,Point b,Point c) ///外接圆圆心坐标
{
Point p;
double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1*a1 + b1*b1)/;
double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2*a2 + b2*b2)/;
double d = a1*b2 - a2*b1;
p.x = a.x + (c1*b2 - c2*b1)/d, p.y=a.y + (a1*c2 -a2*c1)/d;
return p;
}
bool judge(Point a,Point b,Point c,Point p){ ///此模板判断点 p 是否在两条射线 ab 和 ac 之间(但是p点不在 ab或者 ac上)
if(cross(b,c,a)>&&cross(p,a,c)<&&cross(p,a,b)>){ ///b 在 c 的逆时针方向
return true;
}
if(cross(b,c,a)<&&cross(p,a,c)>&&cross(p,a,b)<){ ///b 在 c 的顺时针方向
return true;
}
return false;
}
bool judge1(Point a,Point b,Point c,Point p){ ///此模板判断点 p 是否在两条射线 ab 和 ac 之间(p点可以在 ab或者 ac上)
if(cross(b,c,a)>&&cross(p,a,c)<=&&cross(p,a,b)>=){ ///b 在 c 的逆时针方向
return true;
}
if(cross(b,c,a)<&&cross(p,a,c)>=&&cross(p,a,b)<=){ ///b 在 c 的顺时针方向
return true;
}
return false;
}
int main()
{
Point a,b,c,p;
int t = ;
freopen("a.in","r",stdin);
freopen("a.txt","w",stdout);
while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&p.x,&p.y)!=EOF)
{ Point circle = waixin(a,b,c);
double r = dis(circle,a);
double ans = min(dis(p,a),dis(p,c));
double op = dis(circle,p);
if(fabs(*r-dis(a,c))<eps){ ///平角特殊处理
if(cross(p,c,circle)*cross(b,c,circle)>=){
ans = min(ans,fabs(op-r));
}
printf("Case %d: %.3lf\n",t++,ans);
continue;
}
if(judge(circle,a,c,b)) ///劣弧
{
if(judge1(circle,a,c,p)) ans = min(ans,fabs(op-r));
}
else
{
if(!judge(circle,a,c,p)) ans = min(ans,fabs(op-r));
}
printf("Case %d: %.3lf\n",t++,ans);
}
}
标程:
// Rujia Liu
#include<cmath>
#include<cstdio>
#include<iostream> using namespace std; const double PI = acos(-1.0);
const double TWO_PI = * PI;
const double eps = 1e-; inline double NormalizeAngle(double rad, double center = PI) {
return rad - TWO_PI * floor((rad + PI - center) / TWO_PI);
} inline int dcmp(double x) {
if(fabs(x) < eps) return ; else return x < ? - : ;
} struct Point {
double x, y;
Point(double x=, double y=):x(x),y(y) { }
}; typedef Point Vector; inline Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
inline Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); } inline double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
inline double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
inline double Length(Vector A) { return sqrt(Dot(A, A)); } // 外接圆圆心。假定三点不共线
Point get_circumscribed_center(Point p1, Point p2, Point p3) {
double bx = p2.x - p1.x;
double by = p2.y - p1.y;
double cx = p3.x - p1.x;
double cy = p3.y - p1.y;
double d = * (bx * cy - by * cx);
Point p;
p.x = (cy * (bx * bx + by * by) - by * (cx * cx + cy * cy)) / d + p1.x;
p.y = (bx * (cx * cx + cy * cy) - cx * (bx * bx + by * by)) / d + p1.y;
return p;
} double DistanceToArc(Point a, Point start, Point mid, Point end) { ///点到圆弧的距离
Point p = get_circumscribed_center(start, mid, end);
bool CCW = dcmp(Cross(mid - start, end - start)) > ;
double ang_start = atan2(start.y-p.y, start.x-p.x);
double ang_end = atan2(end.y-p.y, end.x-p.x);
double r = Length(p - start);
double ang = atan2(a.y-p.y, a.x-p.x);
bool inside;
if(CCW) {
inside = NormalizeAngle(ang - ang_start) < NormalizeAngle(ang_end - ang_start);
} else {
inside = NormalizeAngle(ang - ang_end) < NormalizeAngle(ang_start - ang_end);
}
if(inside) {
return fabs(r - Length(p - a));
}
return min(Length(a - start), Length(a - end));
} int main() {
int kase = ;
double x1, y1, x2, y2, x3, y3, xp, yp;
while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> xp >> yp) {
double ans = DistanceToArc(Point(xp,yp), Point(x1,y1), Point(x2,y2), Point(x3,y3));
printf("Case %d: %.3lf\n", ++kase, ans);
}
return ;
}