hdu 4454 Stealing a Cake (三分)

Stealing a CakeTime Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1164    Accepted Submission(s): 320

Problem DescriptionInputOutputSample InputSample OutputSource#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>//#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 105#define MAXN 10005#define mod 1000000007#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 0.00000001using namespace std;int n,m;double x,y,xr,yr,r,x1,Y1,x2,y2,ans;double le,ri,mid,mmid;double caldist(double xx1,double YY1,double xx2,double yy2){ return sqrt((xx1-xx2)*(xx1-xx2)+(YY1-yy2)*(YY1-yy2));}double getdist(double k){ int i,j; double xx,yy,d1,d2; xx=xr+r*cos(k); yy=yr+r*sin(k); d1=caldist(xx,yy,x,y); d2=INF; if(xx>=x1&&xx<=x2||yy>=Y1&&yy<=y2) { if(xx>=x1&&xx<=x2) { d2=min(d2,fabs(yy-Y1)); d2=min(d2,fabs(yy-y2)); } else { d2=min(d2,fabs(xx-x1)); d2=min(d2,fabs(xx-x2)); } } else { d2=min(d2,caldist(xx,yy,x1,Y1)); d2=min(d2,caldist(xx,yy,x2,y2)); d2=min(d2,caldist(xx,yy,x1,y2)); d2=min(d2,caldist(xx,yy,x2,Y1)); } return d1+d2;}void solve(){ int i,j; double d1,d2,tle=le,tri=ri; while(ri-le>eps) { mid=(le+ri)/2.0; mmid=(mid+ri)/2.0; d1=getdist(mid); d2=getdist(mmid); if(d1<d2) ri=mmid; else le=mid; } ans=d1; le=tri; ri=tle+2*pi; while(ri-le>eps) { mid=(le+ri)/2.0; mmid=(mid+ri)/2.0; d1=getdist(mid); d2=getdist(mmid); if(d1<d2) ri=mmid; else le=mid; } ans=min(ans,d1);}void presolve(){ int i,j; double xx1=x1,YY1=Y1,xx2=x2,yy2=y2,tmp; x1=min(xx1,xx2); Y1=min(YY1,yy2); x2=max(xx1,xx2); y2=max(YY1,yy2); xx1=xr-x; YY1=yr-y; tmp=2*xx1/(2*sqrt(xx1*xx1+YY1*YY1)); le=pi/2+acos(tmp); ri=le+pi;}int main(){ int i,j; while(scanf("%lf%lf",&x,&y)) { if(x==0&&y==0) break ; scanf("%lf%lf%lf%lf%lf%lf%lf",&xr,&yr,&r,&x1,&Y1,&x2,&y2); presolve(); solve(); printf("%.2f\n",ans); } return 0;}