AOJ 2327: Sky Jump

ブログに記事を書きます 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");
	}
}