首页 > 代码库 > 【二分】Petrozavodsk Winter Training Camp 2017 Day 1: Jagiellonian U Contest, Monday, January 30, 2017 Problem A. The Catcher in the Rye

【二分】Petrozavodsk Winter Training Camp 2017 Day 1: Jagiellonian U Contest, Monday, January 30, 2017 Problem A. The Catcher in the Rye

一个区域,垂直分成三块,每块有一个速度限制,问你从左下角跑到右上角的最短时间。

将区域看作三块折射率不同的介质,可以证明,按照光路跑时间最短。

于是可以二分第一个入射角,此时可以推出射到最右侧边界上的位置,看什么时候恰好射到右上角即可。

这份sb代码貌似挂精度了。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define EPS 0.0000000001
int T,h,a,b,c,va,vb,vc;
double t1,t2,t3;
bool check(double sina){
	double sinb=sina*(double)vb/(double)va;
	if(sinb-1.0>-EPS){
		return 1;
	}
	double sinc=sinb*(double)vc/(double)vb;
	if(sinc-1.0>-EPS){
		return 1;
	}
	double y1=(double)a*sina/sqrt(1.0-sina*sina);
	double y2=(double)b*sinb/sqrt(1.0-sinb*sinb);
	double y3=(double)c*sinc/sqrt(1.0-sinc*sinc);
	t1=y1/sina/(double)va;
	t2=y2/sinb/(double)vb;
	t3=y3/sinc/(double)vc;
	return y1+y2+y3-(double)h>-EPS;
}
int main(){
//	freopen("a.in","r",stdin);
	scanf("%d",&T);
	for(int zu=1;zu<=T;++zu){
		scanf("%d%d%d%d%d%d%d",&h,&a,&b,&c,&va,&vb,&vc);
		double l=EPS,r=1.0-EPS;
		while(r-l>EPS){
			double mid=(l+r)/2.0;
			if(check(mid)){
				r=mid;
			}
			else{
				l=mid+EPS;
			}
		}
		check(l);
		printf("%.7f\n",t1+t2+t3);
	}
	return 0;
}

【二分】Petrozavodsk Winter Training Camp 2017 Day 1: Jagiellonian U Contest, Monday, January 30, 2017 Problem A. The Catcher in the Rye