UVa 11726 Crime Scene

問題

n個の図形が与えられる。
それぞれの図形は半径r[i], 中心が(x[i], y[i])の円か、
それぞれの頂点が(x[i_0], y[i_0])..., (x[i_k-1], y[i_k-1])k[i]角形どちらか。

この図形の凸包の長さを求めよ。

制約条件

n≦100
k[i]≦10
答えは小数点以下6桁まで出力せよ。

方針

円を多角形で近似して凸包を取る。
これだと全然精度が足りないので、円弧由来の部分は円弧に戻して長さを出す。
円と多角形の接点も、その部分だけ計算しなおす。
円と円の共通接線も、その部分だけ計算しなおす。

すると精度のいい答えが出る。

円弧は、「最初にその円に入った場所」を覚えておいて、円から出るときに見ればよい。
（最後の円弧だけは別個に計算して足す）

周で計算をし始めるのは、円から出る場所が楽。

で、円から出る場所がない場合は、
全部の点が一つの円だけの場合か、円が一つもない場合。
これはそれぞれ適当に計算すればよい。

ソースコード

inline P getp(){
	double x, y;
	cin >> x >> y;
	return P(x, y);
}

int main(){
	int CS; cin >> CS;
	
	rep(cs, CS){
		
		const int SPLIT = 500;
		int n;
		vector<P> c;
		vector<double> r;
		map<P, int> cid;
		
		vector<P> ps;
		double ans = 0;
		
		cin >> n;
		rep(i, n){
			char t; cin >> t;
			if(t == 'c'){
				c.pb(getp());
				double x; cin >> x;
				r.pb(x);
				
				rep(j, SPLIT){
					P p(c.back());
					double u = 2 * PI * j / SPLIT;
					p += x * P(cos(u), sin(u));
					
					ps.pb(p);
					cid[p] = (int)r.size() - 1;
				}
			}
			else{
				int k; cin >> k;
				rep(j, k) ps.pb(getp());
			}
		}
		
		ps = convex_hull(ps);
		P in_p(INF, INF);
		
		int start = -1;
		rep(i, ps.size()) if(cid.count(ps[i])){
			if(!cid.count(ps[(i + 1) % ps.size()]) ||
				cid[ps[i]] != cid[ps[(i + 1) % ps.size()]]){
					
				start = i;
				break;
			}
		}
		if(start < 0){
			//1 一個の円だけからなる
			if(cid.count(ps[0])){
				rep(i, ps.size()) assert(cid.count(ps[i]) && cid[ps[i]] == cid[ps[0]]);
				ans = 2 * PI * r[cid[ps[0]]];
				goto END;
			}
			//2 全部多角形上
			rep(i, ps.size()) assert(!cid.count(ps[i]));
			start = 0;
		}
		
		rep(ii, ps.size()){
			int i = (start + ii) % ps.size();
			P p = ps[i], q = ps[(i + 1) % ps.size()];
			
			
			if(!cid.count(p) && !cid.count(q)){ //多角形だけの部分
				ans += abs(p - q);
			}
			else if(cid.count(p) != cid.count(q)){ //多角形-円の部分
				
				bool out = 1;
				
				if(cid.count(q)){
					swap(p, q);
					out = 0;
				}
				
				int id = cid[p];
				P pp = nearest_tanCP(c[id], r[id], p, q);
				ans += abs(pp - q);
				
				if(out){
					if(in_p.real() == INF) continue;
					
					double a = arg(in_p - c[id]);
					double b = arg(pp - c[id]);
					if(a > b) b += 2 * PI;
					
					ans += r[id] * (b - a);
				}
				else in_p = pp;
			}
			else if(cid.count(p) && cid.count(q)){ //両方円
				
				int pid = cid[p], qid = cid[q];
				if(pid == qid) continue; //弧は後で計算
				
				L l = nearest_tanCC(c[pid], r[pid], c[qid], r[qid], p, q);
				ans += abs(l[0] - l[1]);
				
				if(in_p.real() < INF){
					
					double a = arg(in_p - c[pid]);
					double b = arg(l[0] - c[pid]);
					if(a > b) b += 2 * PI;
					
					ans += r[pid] * (b - a);
				}
				in_p = l[1];
			}
		}
		
		if(in_p.real() < INF){
			P p(ps[start]);
			P q(ps[(start + 1) % ps.size()]);
			
			assert(cid.count(p));
			int id = cid[p];
			
			if(cid.count(q)){
				L l = nearest_tanCC(c[cid[p]], r[cid[p]], c[cid[q]], r[cid[q]], p, q);
				p = l[0];
			}
			else{
				p = nearest_tanCP(c[cid[p]], r[cid[p]], p, q);
			}
			
			double a = arg(in_p - c[id]);
			double b = arg(p - c[id]);
			if(a > b) b += 2 * PI;
			
			ans += r[id] * (b - a);
		}
		
		END:
		printf("Case #%d: %.6f\n", cs + 1, ans);
	}
	return 0;
}