題意:
? ? ? 求點到圓,然后在到矩形的最短路.


思路:

? ? ? 把圓切成兩半,然后對于每一半這個答案都是凸性的,最后輸出兩半中小的那個就行了,其中有一點,就是求點到矩形的距離,點到矩形的距離就是點到矩形四條邊距離中最小的哪一個,求的方法有很多,一開始想都沒想直接敲了個三分(這樣就是兩重三分了)跑了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 三分 求点到圆,然后在到矩形的最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。