ブログに記事を書きます Advent Calendar 2014 - Adventarの3日目の記事です。
行きたい場所のx座標について、最もy座標が小さいときと最もy座標が大きいときの間に行きたい場所のy座標があればOK.前者は自明。後者を考える。
まず、放物線の式になおす。
それぞれの移動に対して、平均の傾きをなるべく大きくしたい。具体的にはこれらのうちの最小値を最大化すればよい。
この平均の傾きで二分探索する。
平均の傾きからxの移動量を求めて、これで行きたいx座標まで到達できるかどうかを判定すればよい。
後は計算しておわり。
#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; double x[1100]; double y[1100]; double eps=1e-9; int main(){ int a; while(scanf("%d",&a),a){ for(int i=0;i<a;i++)scanf("%lf%lf",x+i,y+i); double gx,gy;scanf("%lf%lf",&gx,&gy); double low=999999999; for(int i=0;i<a;i++){ double t=gx/x[i]; low=min(low,-4.9*t*t+y[i]*t); } double left=-999999999; double right=999999999; for(int i=0;i<100;i++){ double M=(left+right)/2; double at=0; for(int j=0;j<a;j++){ if(x[j]*M>y[j])continue; double dx=(y[j]/x[j]-M)*(x[j]*x[j]/9.8); at+=dx; } if(at>gx){ left=M; }else{ right=M; } } double ty=0; for(int i=0;i<a;i++){ if(x[i]*left>y[i])continue; double dx=(y[i]/x[i]-left)*(x[i]*x[i]/9.8); ty+=-4.9/x[i]/x[i]*dx*dx+y[i]/x[i]*dx; } //printf("%f %f\n",low,ty); if(low-eps<gy&&gy<ty+eps)printf("Yes\n"); else printf("No\n"); } }
