UOA1033: Kuru-Kuru Robot

ACM-ICPC Japan Domestic Warm Up IのE問題。本番中は開きもしませんでした。
角度の計算を間違えた以外にはバグも出さず、一発でAcceptされました。本番中にDをスルーしてこっちやってたら解けてたと思います。というか、明らかにDより簡単な気が。

線分アレンジメントしてダイクストラするだけ。(位置)*(向き)がノードになるけれども、向きを角度として扱うと実装も大変で誤差にも弱くなる。「どこから来たか」を向きの代わりに持てば実装が簡単で幸せになれる。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <complex>

using namespace std;

#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define ALL(c) (c).begin(), (c).end()
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)

typedef vector<int> vint;

const double eps=1e-9;
const double inf=1e256;
const double pi=3.1415926535897932;

typedef complex<double> pt;
struct seg{ pt s,d; };
typedef seg line;

typedef vector<pt> gon;

inline pt dir(seg s){ return s.d-s.s; }
inline bool eq(double a,double b){ return fabs(a-b)<eps; }
inline bool pteq(pt a,pt b){ return eq(real(a),real(b)) && eq(imag(a),imag(b));}

namespace std{
  bool operator<(const pt &a,const pt b){
    return a.real()+eps<b.real() || 
      (eq(a.real(),b.real()) && a.imag()+eps<b.imag());
  }
};


inline double dot  (pt a,pt b){ return real(conj(a)*b); }
inline double cross(pt a,pt b){ return imag(conj(a)*b); }

inline int ccw(line l,pt p){
  p-=l.s;
  double c=cross(dir(l),p);
  if(!eq(c,0)) return (c<0 ? -1 : 1);
  if(dot(dir(l),p)<-eps) return 2;
  if(norm(dir(l))+eps<norm(p)) return -2;
  return 0;
}

inline double angle(pt a,pt b,pt c){
  return arg((a-b)/(c-b));
}

const pt NO=pt(inf,inf);
pt crossPoint(line a,line b){
  double n=cross(b.s-a.s,dir(b)), d=cross(dir(a),dir(b));
  return (eq(d,0) ? NO : a.s+n/d*dir(a));
}

inline bool intersectSS(seg a,seg b){
  return (ccw(a,b.s)*ccw(a,b.d)<=0) && (ccw(b,a.s)*ccw(b,a.d)<=0);
}

typedef vector<pt> vpt;
const int N=1000;

struct state{
  int s,d;
  double cost;
  bool operator>(const state &s) const { return cost > s.cost ;}
};

double compute(vector<seg> &v,pt s,pt d){
  vpt ps;
  REP(i,v.size()) ps.push_back(v[i].s), ps.push_back(v[i].d);
  REP(i,v.size()) REP(j,i) if(intersectSS(v[i],v[j]))
    ps.push_back(crossPoint(v[i],v[j]));
  
  sort(ALL(ps));
  ps.erase(unique(ALL(ps),pteq),ps.end());

  static vint   adj[N];
  REP(i,ps.size()) adj[i].clear();

  REP(i,v.size()){
    vint u;
    REP(j,ps.size()) if(!ccw(v[i],ps[j])) u.push_back(j);
    REP(j,u.size()-1) adj[u[j]].push_back(u[j+1]), adj[u[j+1]].push_back(u[j]);
  }

  static double cost[N][N];
  REP(i,ps.size()) REP(j,ps.size()) cost[i][j]=inf;

  priority_queue<state,vector<state>,greater<state> > qu;
  REP(i,ps.size()) if(pteq(ps[i],s))
    EACH(it,adj[i]) qu.push((state){i,*it,0});

  for(;qu.size();){
    state s=qu.top(); qu.pop();
    if(cost[s.s][s.d]<=s.cost) continue;
    cost[s.s][s.d]=s.cost;

    EACH(it,adj[s.d])
      qu.push((state){s.d,*it,s.cost+pi-abs(angle(ps[s.s],ps[s.d],ps[*it]))});
  }
  
  double result=inf;
  REP(j,ps.size()) if(pteq(ps[j],d))
    REP(i,ps.size()) result=min(result,cost[i][j]);

  return result/pi*180;
}

main(){
  int n;
  while(cin >> n && n){
    vector<seg> v;
    double a,b,c,d;
    REP(i,n){
      cin >> a >> b >> c >> d;
      v.push_back((seg){pt(a,b),pt(c,d)});
    }
    pt src,dst;
    cin >> src.real() >> src.imag() >> dst.real() >> dst.imag();

    double result=compute(v,src,dst);
    if(result<inf/2)
      printf("%.12lf\n",result);
    else
      printf("-1\n");
  }
}