[BOJ/백준] 24957 - Loop of Chocolate

24957번: Loop of Chocolate

---

pi의 소숫점을 오차범위보다 더 크게 잡기

---

---

• 제목

Loop of Chocolate

---

• 조건

시간 제한 : 2 초

메모리 제한 : 1024 MB 

---

• 문제

Let’s make sweets of a fancy shape that is a loop of chocolate.

Figure A.1. A loop of chocolate formed by a union of six spheres

The shape of a loop is formed by a union of a number of spheres of the same size, where every sphere intersects with exactly two others.

Your job is to write a program that, for given the size and the positions of spheres, computes the total volume of the union of the spheres, i.e., the amount of chocolate required for filling the loop formed by the union.

[Hints] Two spheres of the same radius r intersect each other when the distance between their centers, d, is less than 2r. The volume of the intersection is known to be 
 

2 / 3 * pi * (r - d / 2) ^ 2 * (2 * r + d / 2)

The volume of the sphere of radius r is 4 * pi * r ^ 3 / 3.

---

• 입력

The input consists of a single test case of the following format.

 

n r

x_n, y_n, z_n

...

x_n, y_n, z_n

 

 $n$ and $r$ are integers. $n$ is the number of spheres (4 ≤ n ≤ 100). All the spheres has the same radius r (2 ≤ r ≤ 100). (x_k, y_k, z_k) indicates the coordinates of the center of the k-th sphere (k = 1, ... , n). All of x_k, y_k, and z_k are integers between -100 and 100, inclusive.

The k-th and the k + 1-th spheres intersect each other for 1 ≤ k < n. The 1-th and the n-th spheres also intersect. No other pairs of spheres intersect.

---

• 출력

Output in a line the volume of the union of the spheres. Relative error of the output should be within 10^-7.

---

예제 입력1	예제 출력1
6 9 20 0 10 20 10 0 10 20 0 0 20 10 0 10 20 10 0 20	17149.528141

예제 입력2	예제 출력2
4 12 10 10 0 10 -10 0 -10 -10 0 -10 10 0	27813.56696

예제 입력3	예제 출력3
6 9 23 3 13 20 10 0 10 20 0 3 23 13 0 10 20 10 0 20	17470.837758

예제 입력4	예제 출력4
4 2 0 0 0 3 0 0 3 3 0 0 3 0	122.52211349

예제 입력5	예제 출력5
8 70 100 100 0 0 100 0 -100 100 0 -100 0 0 -100 -100 0 0 -100 0 100 -100 0 100 0 0	10220648.1

---

#include <iostream>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <vector>
using namespace std;
#define endl '\n'
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pi 3.1415926535
double distance(tuple<double, double, double> a, tuple<double, double, double> b){
	return sqrt(pow(get<0>(a) - get<0>(b), 2) + pow(get<1>(a) - get<1>(b), 2) + pow(get<2>(a) - get<2>(b), 2));
}
double intersectVolume(tuple<double, double, double> a, tuple<double, double, double> b, double r){
	double d = distance(a, b);
	if(d >= 2 * r) return 0;
	return (double)2 / 3 * pi * pow(r - d / 2, 2) * (2 * r + d / 2);
}
int main() {
    fastio;
    vector<tuple<double, double, double>> dots;
    cout << fixed;
    cout.precision(7);
    int sz, r, x, y, z;
    cin >> sz >> r;
    double sum_Volume = sz * 4 * pi * pow(r, 3) / 3;
    for(int n = 0 ; n < sz ; n++){
    	cin >> x >> y >> z;
    	dots.push_back(make_tuple(x, y, z));
	}
	for(int n = 0 ; n < sz ; n++){
		for(int m = n + 1 ; m < sz ; m++){
			sum_Volume -= intersectVolume(dots[n], dots[m], r);
		}
	}
	cout << sum_Volume << endl;
    return 0;
}