AOJ 2099 Walk under a Scorching Sun

問題

凸多角柱で表されるn個の建物がある
太陽がx軸から反時計回りにθの角度の方向で、高さφの角度にある。

m本の道があって、それぞれの道は線分である。
スタートの点(sx, sy)からゴールの点(gx, gy)へ、道を通って行く。

道のうち太陽の当たっている部分の長さを最小化したい。
道のうち太陽の当たっている部分の長さの最小値を求めよ。

太陽光線は平行であるとしてよい。

制約条件

n≦15
m≦15
各多角形の頂点は10個以下

方針

道同士の交点を最初に全部求める。
道の間に点がある道は分割する。

道ごとに太陽の当たる部分の長さを求める。
これは、建物の一辺が作る影が平行四辺形になることから、
適当に交点を求めたりすれば求まる。

自分は影の作る平行四辺形による、道路の切断を考え、
そこから区間でカバーされてる部分を求める感じでやった。

道ごとのコストがわかったら、グラフを作ってダイクストラする。

ソースコード

const double PI = acos(-1.0);
int n, m;
double phi, theta, len[200], h[100];
vector<G> bs;
vector<L> ss;
vector<P> ps;
vector<vector<pair<int, double> > > e;

int main()
{
	while(cin >> n >> m, n){
		bs.clear(); ss.clear();
		ps.clear(); e.clear();
		
		rep(i, n){
			int k, x, y;
			G g;
			cin >> k >> h[i];
			rep(j, k) cin >> x >> y, g.pb(P(x, y));
			bs.pb(g);
		}
		rep(i, m){
			int x, y, X, Y;
			cin >> x >> y >> X >> Y;
			ss.pb(L(P(x, y), P(X, Y)));
		}
		cin >> theta >> phi;
		theta *= PI / 180; theta += PI;
		phi *= PI / 180;
		
		int sx, sy, tx, ty;
		cin >> sx >> sy >> tx >> ty;
		
		rep(i, m) ps.pb(ss[i][0]), ps.pb(ss[i][1]);
		rep(i, m) rep(j, i) if(intersectSS(ss[i], ss[j])){
			rep(k, 2) rep(l, 2) if(ss[i][k] == ss[j][l]) goto SKIP;
			ps.pb(crosspoint(ss[i], ss[j]));
			SKIP:;
		}
		ps.pb(P(sx, sy)); ps.pb(P(tx, ty));
		sort(all(ps));
		
		rep(i, m){
			rep(j, ps.size()){
				if(abs(ss[i][0] - ps[j]) < EPS || abs(ss[i][1] - ps[j]) < EPS) continue;
				if(!intersectSP(ss[i], ps[j])) continue;
				
				ss.pb(L(ps[j], ss[i][1]));
				ss[i][1] = ps[j];
				m++;
			}
		}
		rep(i, m){
			map<double, int> iv;
			double d = abs(ss[i][0] - ss[i][1]);
			
			rep(j, n){
				P x = h[j] * P(cos(theta), sin(theta)) / tan(phi);
				
				rep(k, bs[j].size()){
					int nk = (k + 1) % bs[j].size();
					G g, s;
					g.pb(bs[j][nk]); g.pb(bs[j][nk] + x);
					g.pb(bs[j][k] + x); g.pb(bs[j][k]);
					
					if(ccw(g[0], g[1], g[2]) != 1) reverse(all(g));
					
					s.pb(ss[i][0]); s.pb(ss[i][1]);
					rep(l, 4) s = convex_cut(s, L(g[l], g[(l + 1) % 4]));
					
					if(s.empty()) continue;
					
					double a = abs(s[0] - ss[i][0]) / d, b = abs(s[1] - ss[i][0]) / d;
					if(a > b) swap(a, b);
					iv[a]++; iv[b + EPS]--;
				}
			}
			
			int cnt = 0;
			double prev = 0, sum = 0;
			iv[1] = 0;
			each(it, iv){
				if(cnt == 0) sum += it->first - prev;
				prev = it->first;
				cnt += it->second;
			}
			len[i] = sum * d;
		}
		
		e.resize(ps.size());
		map<P, int> id;
		rep(i, ps.size()) id[ps[i]] = i;
		
		rep(i, m){
			int a = id[ss[i][0]], b = id[ss[i][1]];
			e[a].pb(mp(b, len[i]));
			e[b].pb(mp(a, len[i]));
		}
		priority_queue<pair<double, int> > q;
		set<int> v;
		q.push(mp(0, id[P(sx, sy)]));
		int goal = id[P(tx, ty)];
		
		while(!q.empty()){
			int c = q.top().second;
			double cost = q.top().first;
			q.pop();
			
			if(v.count(c)) continue;
			v.insert(c);
			if(c == goal){
				printf("%.3f\n", -cost); break;
			}
			
			rep(i, e[c].size()){
				double nc = cost - e[c][i].second;
				q.push(mp(nc, e[c][i].first));
			}
		}
	}
	return 0;
}