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"); } }