ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1157 Roll-A-Big-Ball

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1157&lang=jp

障害物を避けながら玉転がしをするときの玉の大きさ(半径)の最大値を求める問題です。


・解法
玉と複数の障害物との間の距離の最小値が求めたい値をなります。

玉と障害物の位置関係についてですが、問題文の図を見てください。
玉の半径をR,玉と障害物の距離をR'、障害物の高さをHとします。

(a)のとき、つまりR' <= Hのとき、R = R'となります。
(b)のとき、つまりR' > Hのとき、R = (H^2 + R'^2)/2Hとなります。

(b)に関してですが、三平方の定理から上の式を求めることができます。


ソースコード
ライブラリは省略

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cassert>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i, 0, n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1<<29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
typedef complex<double> Point; //Point.real()がx Point.imag()がy
typedef vector<Point> Polygon;
 
//線分
struct Segment{
  Point p1,p2;
  Segment(){}
  Segment(Point p1, Point p2):p1(p1),p2(p2){}
};
 
struct Rectangle{
  int h;
  Segment s1,s2,s3,s4;
  Rectangle(){};
  Rectangle(Segment s1, Segment s2, Segment s3, Segment s4, int h):s1(s1),s2(s2),s3(s3),s4(s4),h(h){}
};

int n;
int sx,sy,gx,gy,h;
Segment path;
Rectangle rectangle[50];
 
double solve(){
  double ans = INF;
  rep(i,n) {
    if(intersectSS(path,rectangle[i].s1)) return 0;
    if(intersectSS(path,rectangle[i].s2)) return 0;
    if(intersectSS(path,rectangle[i].s3)) return 0;
    if(intersectSS(path,rectangle[i].s4)) return 0;
     
    double tmp = INF;
    tmp = min(tmp,distanceSS(path,rectangle[i].s1));
    tmp = min(tmp,distanceSS(path,rectangle[i].s2));
    tmp = min(tmp,distanceSS(path,rectangle[i].s3));
    tmp = min(tmp,distanceSS(path,rectangle[i].s4));
     
    double R;
    if(tmp < rectangle[i].h) R = tmp;
    else R = (rectangle[i].h * rectangle[i].h + tmp * tmp) / (2 * rectangle[i].h);
     
    ans = min(ans,R);
  }
  return ans;
}
 
bool check(){
  Polygon pol;
  pol.push_back(Point(sx,sy));
  pol.push_back(Point(sx,gy));
  pol.push_back(Point(gx,sy));
  pol.push_back(Point(gx,gy));
  return contains(pol,path.p1)==OUT || contains(pol,path.p2)==OUT;
}
 
int main(){
  while(cin >> n, n){
    bool NG = false;
    //input
    cin >> sx >> sy >> gx >> gy;
    path = Segment(Point(sx,sy),Point(gx,gy));
    rep(i,n) {
      cin >> sx >> sy >> gx >> gy >> h;
      if(!check()) NG = true;
      Segment s1 = Segment(Point(sx,sy),Point(sx,gy));
      Segment s2 = Segment(Point(sx,sy),Point(gx,sy));
      Segment s3 = Segment(Point(sx,gy),Point(gx,gy));
      Segment s4 = Segment(Point(gx,sy),Point(gx,gy));
      rectangle[i] = Rectangle(s1,s2,s3,s4,h);
    }
    //output
    double ans = 0;
    if(!NG) ans = solve();
    printf("%.10f\n",ans);
  }
  return 0;
}