CodeForces Round #125 (198C)

CodeForces Round #125 (198C)

       题意抽象：

       有点 p 在初始点 ( px , py ) 起逆时针等速度 p.v 沿着绿色大圆 R 转~~点 Q 在平面上的任意位置 ( 除开灰圆 r 内 ) , 点 Q 可以沿任意方向速度最大为 Q.v 移动...灰圆 r 内部的区域是 Q 不能进入的..问 Q 和 p 最快多久能相遇....

       最基本的思路是二分 ， 因为若 Q 与 p 在t时间能够相遇，那么 >t 的时间，两点必能一直相遇...二分时间..假设现在判断的时间为t,那么可以马上得到 t 时间 p 移动到了哪个点..令这个点为 h..这时就要判断, Q 能否在 <=t  的时间到达h点,若可以的 , 说明答案在 <=t 中 , 否则答案在 >t 中 ...

       那么关键之处就是判断 Q  能否在 <=t  的时间到达h点 , 这里分两种情况 , 若线段 Q-h 不穿过灰圆 , 显然 Q 最快到达 h 点就是两点直线距离除:

       而如果线段 Q-h 穿过了灰圆 , 那么就要绕过灰圆 , 而此时的最佳方案 :

       从 Q 作对于灰圆的切线 , 从 h 作对于灰圆的切线 , 两切点之间 贴着灰圆的边 ( 较短的弧长 ) 过去..易证此时路径是最短的...

       当然这题有很多细节要注意...比如如何求出 t 时间的 h 点..如何判断线段 Q-h 是否过灰圆...如何得到两切点间弧长的大小....

Program：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#define ll long long
#define pi acos(-1)
using namespace std;  
struct node
{double x,y,v,r;
}p,Q,h,D;
double mid,l,r,alp,thelen;
double l1,l2,l3,a1;
double dis(node a,node b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool CorssTheCircle(node a,node b)
{double d1=fabs(a.x*b.y-b.x*a.y)/dis(a,b),d2,d3,d4;if (a1<1e-10 || d1-Q.r>-1e-10) return true; return false;    
} 
double judge(double t)
{double a=p.v*t+alp,t1;h.x=p.r*cos(a); h.y=p.r*sin(a); l1=(Q.x*Q.x)+(Q.y*Q.y);l2=(h.x*h.x)+(h.y*h.y);  l3=(Q.x-h.x)*(Q.x-h.x)+(Q.y-h.y)*(Q.y-h.y);a1=acos((l1+l2-l3)/(2*sqrt(l1)*sqrt(l2)))-acos(Q.r/sqrt(l1))-acos(Q.r/sqrt(l2));if (CorssTheCircle(Q,h))  t1=dis(h,Q);else t1=sqrt(l1-Q.r*Q.r)+sqrt(l2-Q.r*Q.r)+thelen*a1/(2*pi); t1/=Q.v;if (t1<t) return false;return true;
}
int main()
{ while (~scanf("%lf%lf%lf",&p.x,&p.y,&p.v)){ scanf("%lf%lf%lf%lf",&Q.x,&Q.y,&Q.v,&Q.r);thelen=2*pi*Q.r;p.r=sqrt(p.x*p.x+p.y*p.y); D.x=D.y=0;alp=acos(p.x/p.r);if (p.y<0) alp=-alp;p.v/=p.r;  l=0; r=1e+10;while (r-l>1e-12){mid=(l+r)*0.5; if (judge(mid)) l=mid;else  r=mid;}printf("%.9lfn",l);}return 0;
}