ACM-ICPC 2010国内予選 G. レーザー光の反射

ACM-ICPC

G. レーザー光の反射

解法

  • レーザーが当たる鏡の順番を全列挙する
    • 反射回数は高々5で，鏡の枚数も高々5なのでそんなに多くない
  • 各反射順ごとに，レーザーの照射角度を求める
    • 反射順に鏡を選び，照射地点の鏡像を取っていく
    • 最終的に得られる照射地点の像の方向が、照射角度の候補になる
  • 照射角度の候補それぞれについて、実際に照射距離を計算する
    • 光の進行を素直にシミュレーションすれば良い
    • 一番近い反射点を求め，次の照射角を計算していく
    • 候補の計算がいい加減なので、ちゃんとゴールに着くかも調べる必要がある
    • 調べたもののうち，最も照射距離が小さかったものを返す
#include <iostream>
#include <vector>
#include <complex>

using namespace std;

typedef complex<double> P;

struct L {
    P p, q;
    L(P p, P q) : p(p), q(q) {}
};

const double EPS = 1e-8;
const double INF = 1e12;

double dot(P a, P b) { return real(conj(a)*b); }
double cross(P a, P b) { return imag(conj(a)*b); }
double angle(P a, P b) { return arg(conj(a)*b); }

P footPerp(L l, P p) {
    return l.p+(l.q-l.p)*(dot(l.q-l.p,p-l.p) / (abs(l.q-l.p)*abs(l.q-l.p)));
}

P lineShadow(L l, P p){
    return 2.0*footPerp(l, p)-p;
}

bool ssIntersect(L a, L b){
    if(abs(imag((a.q-a.p)/(b.q-b.p)))<EPS) return false;
    return cross(a.q-a.p, b.p-a.p)*cross(a.q-a.p, b.q-a.p) < 0 &&
           cross(b.q-b.p, a.p-b.p)*cross(b.q-b.p, a.q-b.p) < 0;
}

bool lpIntersect(L a, P p){
    return abs(imag((p-a.p)/(a.q-a.p)))<EPS;
}

P ssCrosspoint(L a, L b){
    double A = cross(a.q-a.p, b.q-b.p);
    double B = cross(a.q-a.p, a.q-b.p);
    return b.p + B/A * (b.q-b.p);
}

void check(vector<double> &agl, const vector<L> &vl, const vector<int> &idx, P s, P g){
    for(int i=0;i<idx.size();i++){
        if(lpIntersect(vl[idx[i]], g)) return ;
        g = lineShadow(vl[idx[i]], g);
    }
    agl.push_back(angle(P(1,0), g-s));
}

void dfs(vector<double> &agl, const vector<L> &vl, vector<int> &idx, P s, P g){
    check(agl, vl, idx, s, g);
    if(idx.size()==5) return ;
    for(int i=0;i<vl.size();i++){
        if(!idx.empty()&&idx.back()==i) continue;
        idx.push_back(i);
        dfs(agl, vl, idx, s, g);
        idx.pop_back();
    }
}

double calc(const vector<double> &agl, const vector<L> &vl, P s, P g){
    double res = INF;
    for(int i=0;i<agl.size();i++){
        P cur = s;
        P dir = P(cos(agl[i]), sin(agl[i]));
        double len = 0.0;
        for(int cnt=0; ;cnt++){
            P nxt = cur + 1000.0*dir;
            if(lpIntersect(L(cur, cur+dir), g)&&dot(dir, g-cur)>EPS) nxt = g;
            int idx = -1;
            for(int j=0;j<vl.size();j++){
                if(!lpIntersect(vl[j], cur)&&ssIntersect(L(cur, nxt), vl[j])){
                    idx = j;
                    nxt = ssCrosspoint(L(cur, nxt), vl[j]);
                }
            }
            len += abs(cur-nxt);
            if(abs(nxt-g)<EPS) break;
            if(idx == -1 || cnt == 6){
                len = INF;
                break;
            }
            dir = lineShadow(L(nxt, nxt+(vl[idx].q-vl[idx].p)*P(0,1)), cur) - nxt;
            dir /= abs(dir);
            cur = nxt;
        }
        res = min(res, len);
    }
    return res;
}

int main(){
    int n;
    while(cin >> n, n){
        P s, g;
        vector<L> vl;
        for(int i=0;i<n;i++){
            int px, py, qx, qy; cin >> px >> py >> qx >> qy;
            vl.push_back(L(P(px,py), P(qx,qy)));
        }
        int tx, ty, lx, ly; cin >> tx >> ty >> lx >> ly;
        s = P(tx, ty);
        g = P(lx, ly);
        vector<int> idx;
        vector<double> vd;
        dfs(vd, vl, idx, s, g);
        printf("%.4lf\n", calc(vd, vl, s,g));
    }
}