AOJ-1157: 大玉転がし (Roll-A-Big-Ball)
問題概要
配置された直方体の箱に触れないようにある線分上で玉を転がしたい。最大半径を求める問題。
解法
一目でわかる二分探索。2線分間の距離を求めるライブラリさえもっておけば楽勝。問題文やサンプルがとにかく親切。
#include <cstdio> #include <complex> #include <cmath> #include <algorithm> using namespace std; typedef complex<double> P; const int MAX_N = 59; int N; double SX, SY, GX, GY; double minx[MAX_N], maxx[MAX_N], miny[MAX_N], maxy[MAX_N], hs[MAX_N], ds[MAX_N]; P S, G; const double EPS = 1e-12; double sq(double x){ return x*x; } int sig(double a){ return a==0?0:a>0?1:-1; } double iprod(P p1, P p2){ return (p1.real()*p2.real()) + (p1.imag()*p2.imag()); } double oprod(P p1, P p2){ return (p1.real()*p2.imag()) - (p1.imag()*p2.real()); } double disLP(P p1, P p2, P q){ } double disSP(P p1, P p2, P q){ } bool crsSS(P p1, P p2, P q1, P q2){ } bool init(){ for(int i=0; i<N; i++){ if(crsSS(S,G,P(minx[i],miny[i]),P(minx[i],maxy[i])) || crsSS(S,G,P(minx[i],miny[i]),P(maxx[i],miny[i])) || crsSS(S,G,P(maxx[i],maxy[i]),P(minx[i],maxy[i])) || crsSS(S,G,P(maxx[i],maxy[i]),P(maxx[i],miny[i]))){ return false; } if(minx[i] <= SX && SX <= maxx[i] && miny[i] <= SY && SY <= maxy[i]){ return false; } if(minx[i] <= GX && GX <= maxx[i] && miny[i] <= GY && GY <= maxy[i]){ return false; } } for(int i=0; i<N; i++){ ds[i] = 1e10; ds[i] = min(ds[i], disSP(S,G,P(minx[i],miny[i]))); ds[i] = min(ds[i], disSP(S,G,P(minx[i],maxy[i]))); ds[i] = min(ds[i], disSP(S,G,P(maxx[i],miny[i]))); ds[i] = min(ds[i], disSP(S,G,P(maxx[i],maxy[i]))); ds[i] = min(ds[i], disSP(P(minx[i],miny[i]),P(minx[i],maxy[i]),S)); ds[i] = min(ds[i], disSP(P(minx[i],miny[i]),P(maxx[i],miny[i]),S)); ds[i] = min(ds[i], disSP(P(maxx[i],maxy[i]),P(minx[i],maxy[i]),S)); ds[i] = min(ds[i], disSP(P(maxx[i],maxy[i]),P(maxx[i],miny[i]),S)); ds[i] = min(ds[i], disSP(P(minx[i],miny[i]),P(minx[i],maxy[i]),G)); ds[i] = min(ds[i], disSP(P(minx[i],miny[i]),P(maxx[i],miny[i]),G)); ds[i] = min(ds[i], disSP(P(maxx[i],maxy[i]),P(minx[i],maxy[i]),G)); ds[i] = min(ds[i], disSP(P(maxx[i],maxy[i]),P(maxx[i],miny[i]),G)); } return true; } bool check(double r){ for(int i=0; i<N; i++){ if(ds[i] < sqrt(sq(r) - sq(r-min(r,hs[i])))){ return false; } } return true; } double solve(){ if(!init()){ return 0; } double low = 0.0, high = 1009; for(int i=0; i<100; i++){ double mid = (low + high)*0.5; if(check(mid)) low = mid; else high = mid; } return low; } int main(){ while(scanf("%d",&N),N){ scanf("%lf%lf%lf%lf",&SX,&SY,&GX,&GY); S = P(SX,SY); G = P(GX,GY); for(int i=0; i<N; i++){ scanf("%lf%lf%lf%lf%lf",minx+i,miny+i,maxx+i,maxy+i,hs+i); } printf("%.7f\n",solve()); } return 0; }