AOJ 1279 Geometric Map

AOJ 幾何

問題

線分をつないだ図形が与えられる。
線分の両端点が、他の線分上にある線分は道路であり、
一方の端点のみが他の線分上にある線分は、道路に対する標識である。


標識と道路となす角が90度以上のとき、その道路は角度の大きいほうから小さいほうへ通ることはできない。
スタートとゴールの点の座標が与えられたとき、
ゴールまでの最短経路の頂点を順に出力し、その後に0を出力せよ。
経路が存在しないときは-1だけを出力せよ。


標識と道路のなす角が90度以上というのは、
こういうとき→_/

制約条件

線分の本数≦200
座標は全て整数
線分同士の交点は、必ずどちらか一方の線分の端点である。

方針

まずは全ての線分を道路かどうか判定する。
これは両端点が他の線分上にあるかを見ればいい。


次に全ての道路について、他の道路との交点で道路を分割し、
別々の道路とする。


そしたら、道路の通行制限は、その道路についている標識を全部見るだけでよくなるので、
標識を全部みて、通行制限をかける。


最後にダイクストラ法で、スタートからゴールまでの最短経路を求める。

ソースコード

map<P, int> id;
vector<P> ps;
vector<L> ss;
int n, m, prev[10000];
bool isroad[1000];
vector<vector<pi> > es; // (to, seg id)
int pass[1000]; // 1 : 0 to 1, 2 : 1 to 0

inline void add(const P &p){
	if(!id.count(p)){
		id[p] = m++;
		ps.pb(p);
	}
}
int main(){
  while(cin >> n, n){
  	id.clear();
  	ss.clear();
  	ps.clear();
  	memset(isroad, 0, sizeof(isroad));
  	m = 0;
  	
  	P s, g;
  	cin >> s.real() >> s.imag();
  	cin >> g.real() >> g.imag();
  	add(s); add(g);
  	rep(i, n){
  		P a, b;
  		cin >> a.real() >> a.imag();
  		cin >> b.real() >> b.imag();
  		ss.pb(L(a, b));
  		add(a); add(b);
		}
		
		rep(i, n){
			bool ok[2] = {};
			rep(k, 2) rep(j, n){
				if(i != j && (abs(ss[i][k] - ss[j][0]) < EPS ||
					abs(ss[i][k] - ss[j][1]) < EPS ||
					ccw(ss[i][k], ss[j][0], ss[j][1]) == 2)){
						ok[k] = 1; break;
				}
			}
			isroad[i] = ok[0] && ok[1];
		}
		
		//分割処理
		rep(i, n){
			if(ss[i][1] < ss[i][0]) swap(ss[i][0], ss[i][1]);
			
			vector<P> on;
			rep(j, n) if(isroad[j]) rep(k, 2){
				if(ccw(ss[j][k], ss[i][0], ss[i][1]) == 2) on.pb(ss[j][k]);
			}
			if(on.empty()) continue;
			on.pb(ss[i][0]); on.pb(ss[i][1]);
			sort(all(on));
			on.erase(unique(all(on)), on.end());
			ss[i][1] = on[1];
			rep(j, on.size() - 2){
				isroad[n++] = 1;
				ss.pb(L(on[j+1], on[j+2]));
			}
		}
		
  	es.clear();
  	es.resize(m);
		
		rep(i, n) if(isroad[i]){
			pass[i] = 3;
			int a = id[ss[i][0]], b = id[ss[i][1]];
			es[a].pb(mp(b, 1 + i));
			es[b].pb(mp(a, -1 - i));
			
			rep(j, n) if(!isroad[j] && intersectSS(ss[i], ss[j])){
				
				if(ccw(ss[j][1], ss[i][0], ss[i][1]) == 2) swap(ss[j][0], ss[j][1]);
				if(dot(ss[j][1] - ss[j][0], ss[i][1] - ss[j][0]) >= 0) pass[i] &= ~1;
				if(dot(ss[j][1] - ss[j][0], ss[i][0] - ss[j][0]) >= 0) pass[i] &= ~2;
			}
		}
		
		rep(i, n) prev[i] = -1;
		int start = id[s], goal = id[g];
		
		priority_queue<pair<double, pi> > q;
		q.push(mp(0, mp(start, -2)));
		while(!q.empty()){
			int c = q.top().second.first, p = q.top().second.second;
			double cost = q.top().first; q.pop();
			
			if(prev[c] != -1) continue;
			prev[c] = p;
			if(c == goal){
				vi ans;
				for(; c >= 0; c = prev[c]) ans.pb(c);
				reverse(all(ans));
				rep(i, ans.size()){
					cout << (int)ps[ans[i]].real() << " " << (int)ps[ans[i]].imag() << endl;
				}
				cout << 0 << endl;
				goto END;
			}
			
			rep(i, es[c].size()){
				int to = es[c][i].first, e = es[c][i].second;
				if(prev[to] != -1) continue;
				if(e < 0 && !(pass[-e - 1] >> 1)) continue;
				if(e > 0 && !(pass[e - 1] & 1)) continue;
				e = abs(e) - 1;
				q.push(mp(cost - abs(ss[e][0] - ss[e][1]), mp(to, c)));
			}
		}
		puts("-1");
		END:;
	}
  return 0;
}