首页 > 代码库 > HDU 4454 Stealing a Cake --枚举
HDU 4454 Stealing a Cake --枚举
题意: 给一个点,一个圆,一个矩形, 求一条折线,从点出发,到圆,再到矩形的最短距离。
解法: 因为答案要求输出两位小数即可,精确度要求不是很高,于是可以试着爆一发,暴力角度得到圆上的点,然后求个距离,求点到矩形的距离就是求点到四边的距离然后求个最小值,然后总的取个最小值即可。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define Mod 1000000007#define pi acos(-1.0)#define eps 1e-8using namespace std;#define N 1000107typedef struct Point{ double x,y; Point(double x=0,double y=0):x(x),y(y){} Point(){}}Vector;int sgn(double x){ if(x > eps) return 1; if(x < -eps) return -1; return 0;}Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }Vector operator - (Point A,Point B) { return Vector(A.x-B.x,A.y-B.y); }bool operator == (const Point& a,const Point& b) { return (sgn(a.x-b.x) == 0 && sgn(a.y-b.y) == 0); }double Dot(Vector A,Vector B) { return A.x*B.x + A.y*B.y; }double Cross(Vector A,Vector B) { return A.x*B.y - A.y*B.x; }double Length(Vector A) { return sqrt(Dot(A,A)); }double PtoSeg(Point P,Point A,Point B){ if(A == B) return Length(P-A); Vector V1 = B-A; Vector V2 = P-A; Vector V3 = P-B; if(sgn(Dot(V1,V2)) < 0) return Length(V2); else if(sgn(Dot(V1,V3)) > 0) return Length(V3); else return fabs(Cross(V1,V2))/Length(V1);}int main(){ double X,Y; double Cx,Cy,R; double x1,y1,x2,y2; while(scanf("%lf%lf",&X,&Y)!=EOF) { if(sgn(X) == 0 && sgn(Y) == 0) break; scanf("%lf%lf%lf",&Cx,&Cy,&R); scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); Point A = Point(x1,y1); Point B = Point(x1,y2); Point C = Point(x2,y1); Point D = Point(x2,y2); double delta = 2.0*pi*0.0001; double Min = Mod; for(int Angle=1;Angle<=10000;Angle++) { double ang = delta*Angle; double nx = Cx + R*cos(ang); double ny = Cy + R*sin(ang); double D1 = PtoSeg(Point(nx,ny),A,B); double D2 = PtoSeg(Point(nx,ny),A,C); double D3 = PtoSeg(Point(nx,ny),B,D); double D4 = PtoSeg(Point(nx,ny),C,D); double Dis = sqrt((nx-X)*(nx-X)+(ny-Y)*(ny-Y))+min(min(min(D1,D2),D3),D4); Min = min(Dis,Min); } printf("%.2f\n",Min); } return 0;}
HDU 4454 Stealing a Cake --枚举
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。