ICPC 国内予選2008E 大玉転がし AOJ 1157

解説:

まずそれぞれの障害物について、直線状のコースへの距離の最小値を求める。（つまり、障害物とコースの間の一番短くなるときの距離を求める）。これについては、点と線分の距離を用いて求める。ライブラリについては下記のサイトを参照しました。
qiita.com

また、コースの線分と障害物の周りの長方形の線分（４つある）が交差している場合、コース上に障害物があることになるのでこのときのansは0になる。ここについては下記のサイトを参照しました。
qiita.com

あとはコースと障害物の間の距離と、障害物の高さの情報から各障害物について大玉の最大値が求められるので（２パターンの場合分けが必要。すこし考えればわかるのでここでは自明とする）そのなかの最小値がans。

また、障害物のなかにコースがスッポリ入るというコーナーケースもあるので注意。（ただし、親切なことにサンプルにそのような入力例があるので気づきやすい）

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1,0,-1,-1,-1,0,1,1};
int dy[]={1,1,1,0,-1,-1,-1,0};

double block[55][4];
double h[55];
int n;
double sx,sy,ex,ey;

double min_d2(double x0,double y0,double x1,double y1,double x2,double y2) {
    double a = x2 - x1;
    double b = y2 - y1;
    double a2 = a * a;
    double b2 = b * b;
    double r2 = a2 + b2;
    double tt = -(a*(x1-x0)+b*(y1-y0));
    if( tt < 0 ) {
        return ( (x1-x0)*(x1-x0) + (y1-y0)*(y1-y0) );
    }
    if( tt > r2 ) {
        return ( (x2-x0)*(x2-x0) + (y2-y0)*(y2-y0) );
    }
    double f1 = a*(y1-y0)-b*(x1-x0);
    return ( (f1*f1)/r2 );
}

bool judgeIenter(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy) {
    double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
    double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
    double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
    double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);

    return (tc * td < 0 && ta * tb < 0);
    // return tc * td <= 0 && ta * tb <= 0; // 端点を含む場合
}

double dist(int m){
    bool flag = false;
    double b[4];
    for(int k = 0;k < 4;k++) b[k] = block[m][k];
    flag = ( judgeIenter(sx,sy,ex,ey,b[0],b[1],b[0],b[3]) || flag );
    flag = ( judgeIenter(sx,sy,ex,ey,b[0],b[1],b[2],b[1]) || flag );
    flag = ( judgeIenter(sx,sy,ex,ey,b[0],b[3],b[2],b[3]) || flag );
    flag = ( judgeIenter(sx,sy,ex,ey,b[2],b[1],b[2],b[3]) || flag );
    if(flag)return 0;
    double ret = min_d2(b[0],b[1],sx,sy,ex,ey);
    ret = min(ret,min_d2(b[0],b[3],sx,sy,ex,ey));
    ret = min(ret,min_d2(b[2],b[1],sx,sy,ex,ey));
    ret = min(ret,min_d2(b[2],b[3],sx,sy,ex,ey));

    ret = min(ret,min_d2(sx,sy,b[0],b[1],b[0],b[3]));
    ret = min(ret,min_d2(sx,sy,b[0],b[1],b[2],b[1]));
    ret = min(ret,min_d2(sx,sy,b[0],b[3],b[2],b[3]));
    ret = min(ret,min_d2(sx,sy,b[2],b[1],b[2],b[3]));

    ret = min(ret,min_d2(ex,ey,b[0],b[1],b[0],b[3]));
    ret = min(ret,min_d2(ex,ey,b[0],b[1],b[2],b[1]));
    ret = min(ret,min_d2(ex,ey,b[0],b[3],b[2],b[3]));
    ret = min(ret,min_d2(ex,ey,b[2],b[1],b[2],b[3]));
    return sqrt(ret);
}

int main(){
    
    while(true){
        cin >> n;
        if(n == 0)break;
        cin >> sx >> sy >> ex >> ey;
        if(sx > ex){
            int tmpx = sx,tmpy = sy;
            sx = ex;
            sy = ey;
            ex = tmpx;
            ey = tmpy;
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < 4;j++){
                cin >> block[i][j];
            }
            cin >> h[i];
        }
        double ans = 1000;
        for(int i = 0;i < n;i++){
            double d = dist(i);
    //        cout << i << ":" << d << endl;
            if(d == 0){
                ans = 0;
                break;
            }
            if(block[i][0] <= sx && block[i][2] >= ex && block[i][1] <= min(sy,ey) && block[i][3] >= max(sy,ey)){
                ans = 0;
                break;
            }
            double tmpans;
            if(d <= h[i]){
                tmpans = d;
            }else{
                tmpans = (d*d + h[i]*h[i]) / (2*h[i]);
            }
            if(ans > tmpans) ans = tmpans;
        }
        printf("%f\n",ans);
    //    cout << ans << endl;
    }
}