hdu4454 三分求点到圆,然后在到矩形的最短路

题意:

求点到圆,然后在到矩形的最短路.

思路:

把圆切成两半,然后对于每一半这个答案都是凸性的,最后输出两半中小的那个就行了,其中有一点,就是求点到矩形的距离,点到矩形的距离就是点到矩形四条边距离中最小的哪一个,求的方法有很多,一开始想都没想直接敲了个三分(这样就是两重三分了)跑了890ms AC的,后来看了看人家的都是直接用模板过的,我也找了个模板,结果31ms AC,哎,没事真的多暂歇模板,只有好处没坏处是了..

#include<stdio.h>

#include<math.h>

#include<algorithm>

#define eps 1e-3

double PI=acos(-1.0);

using namespace std;

typedef struct

{

   double x ,y;

}NODE;

typedef struct

{

   NODE A ,B;

}EDGE;

NODE node[10];

EDGE edge[10];

NODE S ,O;

double diss1[10] ,diss2[10];

double R;

bool camp(NODE a ,NODE b)

{

   return a.x < b.x || a.x == b.x && a.y < b.y;

}

double dis(NODE a ,NODE b)

{

   double tmp = pow(a.x - b.x ,2.0) + pow(a.y - b.y ,2.0);

   return sqrt(tmp);

}

double minn(double x ,double y)

{

   return x < y ? x : y;

}

double abss(double x)

{

   return  x > 0 ? x : -x;

}

NODE getnode(double du)

{

   NODE ans;

   ans.x = O.x + R *cos(du);

   ans.y = O.y + R * sin(du);

   return ans;

}   

//**********************************

struct Point

{

    double x,y;

    Point(double xx=0,double yy=0):x(xx),y(yy){}

    Point operator -(const Point p1)

    {

        return Point(x-p1.x,y-p1.y);

    }

    double operator ^(const Point p1)

    {

        return x*p1.x+y*p1.y;

    }

};

double cross(Point a,Point b)

{

    return a.x*b.y-a.y*b.x;

}

inline int sign(double d)

{

    if(d>eps)return 1;

    else if(d<-eps)return -1;

    else return 0;

}

double dis(Point A ,Point B)

{

   return sqrt(pow(A.x - B.x ,2.0) + pow(A.y - B.y ,2.0));

}

double ptoline(Point tp,Point st,Point ed)//求点到线段的距离

{

    double t1=dis(tp,st);

    double t2=dis(tp,ed);

    double ans=min(t1,t2);

    if(sign((ed-st)^(tp-st))>=0 && sign((st-ed)^(tp-ed))>=0)//锐角

    {

        double h=fabs(cross(st-tp,ed-tp))/dis(st,ed);

        ans=min(ans,h);

    }

    return ans;

}

//************************



double search3_2(double L ,double R)

{

   double low ,up ,mid ,mmid;

   NODE now;

   low = L ,up = R;

   while(1)

   {

      mid = (low + up) / 2;

      now = getnode(mid);

      Point A ,B ,C;

      A.x = now.x ,A.y = now.y;

      for(int i = 1 ;i <= 4 ;i ++)

      {

         B.x = edge[i].B.x ,B.y = edge[i].B.y;

         C.x = edge[i].A.x ,C.y = edge[i].A.y;

         diss1[i] = ptoline(A ,B ,C) + dis(S ,now);

      }

      sort(diss1 + 1 ,diss1 + 4 + 1);

      mmid = (mid + up) / 2;

      now = getnode(mmid);

      A.x = now.x ,A.y = now.y;

      for(int i = 1 ;i <= 4 ;i ++)

      {

         B.x = edge[i].B.x ,B.y = edge[i].B.y;

         C.x = edge[i].A.x ,C.y = edge[i].A.y;

         diss2[i] = ptoline(A ,B ,C) + dis(S ,now);

      }

      sort(diss2 + 1 ,diss2 + 4 + 1);

      if(diss1[1] > diss2[1]) low = mid;

      else up = mmid;

      if(abss(low - up) < eps) break;

   }

   return diss1[1];

}

int main ()

{

   while(~scanf("%lf %lf" ,&S.x ,&S.y))

   {

      if(S.x == 0 && S.y == 0) break;

      scanf("%lf %lf %lf" ,&O.x ,&O.y ,&R);

      scanf("%lf %lf %lf %lf" ,&node[1].x ,&node[1].y ,&node[2].x ,&node[2].y);

      node[3].x = node[1].x ,node[3].y = node[2].y;

      node[4].x = node[2].x ,node[4].y = node[1].y;

      sort(node + 1 ,node + 4 + 1 ,camp);

      edge[1].A.x = node[1].x ,edge[1].A.y = node[1].y;

      edge[1].B.x = node[2].x ,edge[1].B.y = node[2].y;

      edge[2].A.x = node[2].x ,edge[2].A.y = node[2].y;

      edge[2].B.x = node[4].x ,edge[2].B.y = node[4].y;

      edge[3].A.x = node[4].x ,edge[3].A.y = node[4].y;

      edge[3].B.x = node[3].x ,edge[3].B.y = node[3].y;

      edge[4].A.x = node[3].x ,edge[4].A.y = node[3].y;

      edge[4].B.x = node[1].x ,edge[4].B.y = node[1].y;

     printf("%.2lf\n" ,minn(search3_2(0 ,PI) ,search3_2(PI ,2*PI)));

   }

   return 0;

}

巴特西

hdu4454 三分求点到圆,然后在到矩形的最短路

最新文章

热门文章

巴特西

hdu4454 三分 求点到圆,然后在到矩形的最短路

最新文章

热门文章

hdu4454 三分求点到圆,然后在到矩形的最短路