Google Code Jam 2009:Round2 Problem D. Watering Plants small

2つのスプリンクラーで円形のPlantに水をやる問題。
Large問題は検討もつかないけど、Smallなら簡単。

n=1のときは、そのPlantの半径がそのまま答え。
n=2のtきは、2つのPlantを比べて大きいほうが答え。
n=3のときは、1つと2つのグループに分けて、それぞれ必要な半径を計算。グループの分け方は3通りだから一瞬ですね。

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cmath>

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;

#define rep(i,a,b) for(int i=a;i<b;i++)

using namespace std;

double sq(double x) {
	return x*x;
}

int solve(int no)
{
	int n;
	cin >> n;
	
	double x[10], y[10], r[10];
	rep(i,0,n) {
		cin >> x[i] >> y[i] >> r[i];
	}
	
	if(n==1) {
		cout << "Case #" << no << ": ";
		printf("%.6f\n", r[0]);
		return 0;
	} else if(n==2) {
		cout << "Case #" << no << ": ";
		printf("%.6f\n", max(r[0], r[1]));
		return 0;
	}
	
	double rmin = 1E10;
	rep(i,0,n) {
		int j = (i+1)%n, k = (i+2)%n;
		double r2 = (sqrt(sq(x[j]-x[k])+sq(y[j]-y[k])) + r[j] + r[k])/2;
		rmin = min(rmin, max(r2, r[i]));
	}
	cout << "Case #" << no << ": ";
	printf("%.6f\n", rmin);
}

int main()
{
	int T;
	cin >> T;
	rep(no,0,T) {
		solve(no+1);
	}
	return 0;
}