首页 > 代码库 > csu-acm 1503: 点到圆弧的距离

csu-acm 1503: 点到圆弧的距离

1503: 点到圆弧的距离

分析:

先判断点和圆心的连线是否在圆弧范围内,如果在,最短距离即到圆心的距离减去半径的绝对值;反之,为到端点的最短距离。

具体看注释

#include <bits/stdc++.h>using namespace std;#define eps 1e-8const double pi=acos(-1);struct Point{    double x,y;    Point(double a=0,double b=0)    {        x=a;        y=b;    }};Point operator - (Point a,Point b){    return Point(a.x-b.x,a.y-b.y);}double dist(Point a,Point b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double multi(Point a,Point b){    return a.x*b.x+a.y*b.y;}double cross(Point a,Point b){    return a.x*b.y-a.y*b.x;}Point TriangleCircumCenter(Point a,Point b,Point c){    Point res;    double a1=atan2(b.y-a.y,b.x-a.x)+pi/2;    double a2=atan2(c.y-b.y,c.x-b.x)+pi/2;    double ax=(a.x+b.x)/2;    double ay=(a.y+b.y)/2;    double bx=(c.x+b.x)/2;    double by=(c.y+b.y)/2;    double r1=(sin(a2)*(ax-bx)+cos(a2)*(by-ay))/(sin(a1)*cos(a2)-sin(a2)*cos(a1));    return Point(ax+r1*cos(a1),ay+r1*sin(a1));}int main(){//    freopen("in.txt","r",stdin);//    freopen("out.txt","w",stdout);    int x1,y1,x2,y2,x3,y3,xp,yp;    int kase=0;    while(~scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&xp,&yp))    {        Point p1=Point(x1,y1);        Point p2=Point(x2,y2);        Point p3=Point(x3,y3);        Point pp=Point(xp,yp);        Point pc=TriangleCircumCenter(p1,p2,p3);    //算圆心        double temp=cross(p2-p1,p3-p1);        if(temp<0)  //如果是顺时针,把p1和p3点互换        {            Point t=p1;            p1=p3;            p3=t;        }        double cosA=multi(p1-pc,p3-pc)/(dist(p1,pc)*dist(p3,pc));        if(fabs(cosA)>1)    //如果fabs(cosA)>1,那么acos(cosA)算出的结果是不合法的        {            if(cosA<0) cosA+=eps;            else cosA-=eps;        }        double maxd=acos(cosA); //算p1-pc与p3-pc的夹角        if(cross(p1-pc,p3-pc)<0 && fabs(cross(p1-pc,p3-pc))>eps)            maxd=2*pi-maxd;        double cosB=multi(p1-pc,pp-pc)/(dist(p1,pc)*dist(pp,pc));        if(fabs(cosB)>1)        {            if(cosB<0) cosB+=eps;            else cosB-=eps;        }        double degree=acos(cosB);   //算p1-pc与pp-pc的夹角        if(cross(p1-pc,pp-pc)<0 && fabs(cross(p1-pc,pp-pc))>eps)            degree=2*pi-degree;        if(degree<maxd)            printf("Case %d: %.3lf\n",++kase,fabs(dist(pp,pc)-dist(p1,pc)));        else            printf("Case %d: %.3lf\n",++kase,min(dist(pp,p1),dist(pp,p3)));    }    return 0;}

 

csu-acm 1503: 点到圆弧的距离