AOJ 1171 : Laser Beam Reflections

問題リンク : Laser Beam Reflections | Aizu Online Judge

解法：
レーザービームを打つ方向を３６０度ちょっとずつずらしながらシュミレーションした
レーザービームを打つ方向さえ決めてしまえばそこからゴールまで到達できるかどうかは一意に定まるので判定しながら距離を計算して最小のものを出力した
EPSを1e-5に設定してループで角度を0.001だけずらしながら計算したらACした

他の人と1.5秒近く差があるのが気掛かり

コード:

int n;
vector<Segment> seg;
Point s,t;

double compute(double rad)
{
  Point e = Point(cos(rad),sin(rad));
  e = e * 1000;
  e = e + s;
  Segment UruruBeam = Segment(s,e);


  double ret = 0;
  Point sp;
  int onSeg = -1;
  sp = s;
  rep(i,6)
    {
      double mdist = inf;
      Point mcp;
      int mp = -1;
      rep(j,n)if(onSeg != j && intersectSS(UruruBeam,seg[j]))
	{
	  Point cp = crosspoint(UruruBeam,seg[j]);
	  double dist = abs(sp-cp);
	  if(!equals(mdist,dist) && mdist > dist)
	    {
	      mdist = dist;
	      mcp = cp;
	      mp = j;
	    }
	}

      if(intersectSP(UruruBeam,t))
	{
	  double dist = abs(sp-t);
	  if(!equals(mdist,dist) && mdist > dist)return ret + dist;
	}

      if(mp == -1)return inf;
	
      onSeg = mp;
      ret += abs(sp-mcp);
      UruruBeam = Segment(mcp,reflection(seg[mp],UruruBeam.p2));
      sp = mcp;

    }
  return inf;
}

int main()
{
  while(scanf("%d",&n),n)
    {
      seg.clear();
      seg.resize(n);
      rep(i,n)scanf("%lf %lf %lf %lf",&seg[i].p1.x,&seg[i].p1.y,&seg[i].p2.x,&seg[i].p2.y);
      scanf("%lf %lf",&t.x,&t.y);
      scanf("%lf %lf",&s.x,&s.y);

      double ans = inf;
      for(double theta=0.0,cnt=0;cnt <= 360000;theta+=0.001,cnt++)
	{
	  ans = min(ans,compute(toRad(theta)));
	}
      printf("%.10lf\n",ans);
    }
  return 0;
}