AOJ : 1212 - Mirror Illusion

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1212
問題文の図のような部屋があり, (0.75,0.25)の位置で, (1.0,0.5)の方向を向いて人が立っている.
また, この部屋には, 鏡がいくつか置いてある.
このとき, 立っている人は, 周りの壁のどこの座標を見るか答えよ.
（もし, 自分が見える場合は, 自分の座標を答えよ）

アルゴリズム

解法１

• 幾何で解く
• 現在の位置, 向いている方向から, 次はどの鏡で反射するか求める
• 鏡に反射する前に, 自分が見えるならば, 自分の座標を出力.
• 鏡に反射しないならば, 壁の座標を答えればいい.

解法２

• 人の視線は, 鏡の面に向かって必ず入射角45度.
• 幾何なんてしなくても, この性質を利用してシミュレーションで解ける.

プログラム

バカみたいに, 解法１で解いてしまいました.

typedef complex<double> P;

const double INF = 99999;

bool intersectSS(P a,P b,P c,P d){...}
bool intersectSP(P a,P b,P p){...}
P crosspoint(P a,P b,P c,P d){...}

int n;
char dch[150];
P from[150],to[150];

//自分の座標と, 向く方向を更新
//now:自分の位置, dp:視線の先の座標
void getNext(P &now,P &dp,P p,int mirror){
  dp = now;

  if(dch[mirror] == 'y'){
    double dist = abs(now.imag() - p.imag());
    if(now.imag() > p.imag()){
      dp.imag() -= dist * 2;
    }
    else{
      dp.imag() += dist * 2;
    }
  }
  else{
    double dist = abs(now.real() - p.real());
    if(now.real() > p.real()){
      dp.real() -= dist * 2;
    }
    else{
      dp.real() += dist * 2;
    }
  }
  now = p;
  dp = now + INF * (dp - now); //無限に伸ばした線分にする
}

int main(){
  while(cin>>n,n>=0){
    rep(i,n){
      double x,y;
      cin>>dch[i]>>x>>y;
      from[i] = P(x,y);
      to[i] = (dch[i] == 'x' ? P(x+1,y) : P(x,y+1));
    }

    //壁4つ
    from[n] = to[n+3] = P(0,0);
    from[n+1] = to[n] = P(8,0);
    from[n+2] = to[n+1] = P(8,8);
    from[n+3] = to[n+2] = P(0,8);

    //now:自分がいる場所, dp:視線の先の座標
    //視線は, nowから伸びる無限の線分として表す
    P now(0.75,0.25);
    P dp = now + INF * (P(1,0.5) - now);
    bool himself = false;

    while(1){
      int minIdx = -1;
      P minP;
      double minDist = INF;

      //視線と衝突する, 現在いる場所から一番近い鏡を探す
      rep(i,n){
        if(intersectSS(from[i],to[i],now,dp)){
          P p = crosspoint(from[i],to[i],now,dp);
          double dist = abs(p - now);
          if(dist > EPS && dist < minDist){
            minIdx = i;
            minDist = dist;
            minP = p;
          }
        }
      }
      //視線と初期位置が衝突した場合
      if(intersectSP(now,dp,P(0.75,0.25))){
        double dist = abs(P(0.75,0.25) - now);
        if(dist > EPS && dist < minDist){
          himself = true;
          break;
        }
      }

      //壁が見えたとき
      if(minIdx == -1) break;

      getNext(now,dp,minP,minIdx);
    }

    if(himself){
      printf("75 25\n");
      continue;
    }

    //壁の座標を求める
    rep(i,4){
      if(intersectSS(from[n+i],to[n+i],now,dp)){
        P p = crosspoint(from[n+i],to[n+i],now,dp);
        if(abs(p - now) < EPS) continue;
        printf("%d %d\n",(int)(p.real()*100),(int)(p.imag()*100));
      }
    }
  }
}