首页 > 代码库 > 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;}
View Code

 

HDU 4454 Stealing a Cake --枚举