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