Lampyridae Teleportae
题目:http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2169
题意:给你初始点和每次最长的行走长度,再给你几个萤火虫突然闪现的位置(已按时间顺序排序),问能否抓到萤火虫。
题解:因为每次都是尽量向当前闪现的点前进,所以按题意模拟即可。
代码:
#include<cstdio> #include<cstring> #include<cmath> using namespace std; #define eps (1e-8) struct node { double x,y; }st,en; double distant(node a,node b)//计算两点距离 { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main() { double x,y,r; for(int cas=1;scanf("%lf%lf%lf",&r,&st.x,&st.y);++cas) { if(fabs(r+st.x+st.y)<eps) break; bool flag=false; printf("Firefly %d ",cas); for(;scanf("%lf%lf",&en.x,&en.y);) { if(fabs(en.x+1)<eps&&fabs(en.y+1)<eps) break; if(flag) continue;//已经抓到了,无需继续计算 if(distant(st,en)<=r+1)//判断能否抓到 { flag=true; printf("caught at (%.0f,%.0f)\n",en.x,en.y); continue; } //计算这次的终点 double a=en.x-st.x; double b=en.y-st.y; double c=distant(st,en); st.x=st.x+(r/c*a); st.y=st.y+(r/c*b); } if(!flag) printf("not caught\n"); } return 0; }