<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

266. Berlion
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Far far away in the galaxy there is a planet called Berlion. The legend says that the Precursors left rich heritage on the planet. There are a lot of galactic races competing to claim the heritage. By the will of mighty Precursors each civilization has only one chance to land on the planet and explore small area of the surface. Powerful guards left by Precursors keep competitors from violation of the will. No race can compete the guards in a combat.
Recently race of bertonoids has built two super-scanners to scan the surface for artifacts. Bertonoids set up scanners in two locations of the space, where the guards hopefully won't detect them. You can assume that the planet has the form of a sphere and the scanners are points.
You, as intern in Forecast Department, have to find the area of the surface the scanners can explore. The scanners can explore only the directly visible part of the surface (you can assume that there are no any other objects in the sector with Berlion and scanners).
So your task is to find the area of that part of the planet surface, from which at least one of the scanners is visible.

Input
The first line of the input file contains the integer number R -- the radius of the planet (1 <= R <= 10). The second line contains the coordinates of the first scanner relatively to the center of the planet -- 3 numbers -- the distances along the x, y and z axes of an ortogonal normalized coordinate system. The third line contains the coordinates of the second scanner in the same format. All coordinates are integers and do not exceed 100 by the absolute value. Both scanners are located at the distance not less than 10-2 above the planet surface.

Output
Output the visible area of the planet surface. The answer should be rounded to 3 decimal digits.

Sample test(s)

Input
Test #1

1
0 0 100
0 100 0

Test #2

1
0 0 100
0 0 -100

Output
Test #1

9.362

Test #2

12.441
Author:	Ilya V. Elterman
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

<|response|>
## 1. Abridged problem statement

We are given a sphere of radius `R` centered at the origin and two scanner points outside the sphere.

Each scanner can see the part of the sphere surface that is directly visible from its position. We need to compute the total surface area visible from at least one of the two scanners.

Output the answer rounded to 3 decimal digits.

---

## 2. Key observations needed to solve the problem

### Observation 1: One scanner sees a spherical cap

Let a scanner be at position vector `p`.

Let:

```text
d = |p|
u = p / d
```

where `u` is the unit vector from the sphere center toward the scanner.

A point `x` on the sphere is visible from the scanner if the segment from `x` to the scanner does not go through the sphere.

The boundary of visibility is the tangent circle from the scanner to the sphere.

On the unit sphere, the visible region is:

```text
n · u >= R / d
```

where `n = x / R`.

So the scanner sees a spherical cap whose angular radius `a` satisfies:

```text
cos(a) = R / d
```

The area of this cap on a sphere of radius `R` is:

```text
2πR²(1 - cos(a))
```

Since `cos(a) = R / d`, the cap area is:

```text
2πR²(1 - R / d)
```

---

### Observation 2: We need the union of two spherical caps

Each scanner sees one cap.

Let:

```text
a = angular radius of cap 1
b = angular radius of cap 2
t = angular distance between the cap centers
```

The answer is:

```text
area(cap1 ∪ cap2) = area(cap1) + area(cap2) - area(cap1 ∩ cap2)
```

So the main challenge is computing the intersection area of two spherical caps.

---

### Observation 3: There are three possible relationships between the caps

#### Case 1: Disjoint caps

If:

```text
t >= a + b
```

the caps do not overlap.

Then:

```text
intersection = 0
```

#### Case 2: One cap fully contains the other

If:

```text
t + min(a, b) <= max(a, b)
```

then the smaller cap lies completely inside the larger cap.

Then:

```text
intersection = area of smaller cap
```

#### Case 3: Partial overlap

Otherwise, the intersection is a spherical lens.

We compute its area using spherical geometry.

---

## 3. Full solution approach based on the observations

Let the scanner positions be `p1` and `p2`.

First compute their distances from the origin:

```text
d1 = |p1|
d2 = |p2|
```

The angular radii of the two visible caps are:

```text
a = acos(R / d1)
b = acos(R / d2)
```

Let:

```text
ca = cos(a) = R / d1
cb = cos(b) = R / d2
```

Also compute:

```text
sa = sin(a)
sb = sin(b)
```

The angle `t` between the two cap centers is the angle between vectors `p1` and `p2`:

```text
cos(t) = (p1 · p2) / (|p1| |p2|)
```

Then:

```text
t = acos(cos(t))
```

The individual cap areas are:

```text
area1 = 2πR²(1 - ca)
area2 = 2πR²(1 - cb)
```

Now compute the intersection.

---

### Partial overlap formula

In the partial overlap case, the two caps form a spherical lens.

Define:

```text
ct = cos(t)
st = sin(t)
```

Let `psi_a` be half the angular span of the lens arc along cap 1's boundary, measured around cap 1's center.

Similarly, let `psi_b` be the corresponding half-span for cap 2.

Using spherical trigonometry:

```text
cos(psi_a) = (cb - ca * ct) / (sa * st)
cos(psi_b) = (ca - cb * ct) / (sb * st)
```

Also define `gamma` as the angle between the two boundary tangent directions at an intersection point:

```text
cos(gamma) = (ct - ca * cb) / (sa * sb)
```

Then the lens area on the sphere of radius `R` is:

```text
intersection =
R² * (2(π - gamma) - 2 * psi_a * ca - 2 * psi_b * cb)
```

Finally:

```text
answer = area1 + area2 - intersection
```

Because floating-point calculations may produce values like `1.0000000002`, every argument passed to `acos` should be clamped into `[-1, 1]`.

The algorithm is constant time:

```text
Time complexity: O(1)
Memory complexity: O(1)
```

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1.0);
const double EPS = 1e-12;

struct Vec3 {
    double x, y, z;

    double dot(const Vec3& other) const {
        return x * other.x + y * other.y + z * other.z;
    }

    double norm() const {
        return sqrt(dot(*this));
    }
};

double clampCos(double x) {
    if (x < -1.0) return -1.0;
    if (x > 1.0) return 1.0;
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    double R;
    Vec3 p1, p2;

    cin >> R;
    cin >> p1.x >> p1.y >> p1.z;
    cin >> p2.x >> p2.y >> p2.z;

    // Distances from sphere center to scanners.
    double d1 = p1.norm();
    double d2 = p2.norm();

    // For a scanner at distance d, the visible cap has angular radius a:
    // cos(a) = R / d.
    double ca = R / d1;
    double cb = R / d2;

    ca = clampCos(ca);
    cb = clampCos(cb);

    double a = acos(ca);
    double b = acos(cb);

    double sa = sqrt(max(0.0, 1.0 - ca * ca));
    double sb = sqrt(max(0.0, 1.0 - cb * cb));

    // Angle between scanner directions.
    double ct = p1.dot(p2) / (d1 * d2);
    ct = clampCos(ct);

    double t = acos(ct);
    double st = sqrt(max(0.0, 1.0 - ct * ct));

    // Area of each cap.
    double area1 = 2.0 * PI * R * R * (1.0 - ca);
    double area2 = 2.0 * PI * R * R * (1.0 - cb);

    double intersection = 0.0;

    // Case 1: caps are disjoint or only tangent.
    if (t >= a + b - EPS) {
        intersection = 0.0;
    }

    // Case 2: one cap is completely inside the other.
    else if (t + min(a, b) <= max(a, b) + EPS) {
        intersection = min(area1, area2);
    }

    // Case 3: partial overlap, intersection is a spherical lens.
    else {
        // Half angular span of cap 1 boundary arc inside cap 2.
        double psiA = acos(clampCos((cb - ca * ct) / (sa * st)));

        // Half angular span of cap 2 boundary arc inside cap 1.
        double psiB = acos(clampCos((ca - cb * ct) / (sb * st)));

        // Angle between boundary tangent directions at an intersection point.
        double gamma = acos(clampCos((ct - ca * cb) / (sa * sb)));

        // Lens area formula, scaled by R^2.
        intersection = R * R * (
            2.0 * (PI - gamma)
            - 2.0 * psiA * ca
            - 2.0 * psiB * cb
        );

        // Numerical safety: avoid tiny negative values.
        if (intersection < 0.0 && intersection > -1e-9) {
            intersection = 0.0;
        }
    }

    double answer = area1 + area2 - intersection;

    cout << fixed << setprecision(3) << answer << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import math
import sys


EPS = 1e-12


def clamp_cos(x):
    """
    Clamp x into [-1, 1].

    This is necessary before acos because floating-point arithmetic
    may produce values slightly outside the valid range.
    """
    return max(-1.0, min(1.0, x))


def dot(a, b):
    """
    Dot product of two 3D vectors.
    """
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def norm(a):
    """
    Euclidean length of a 3D vector.
    """
    return math.sqrt(dot(a, a))


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    R = float(data[0])

    p1 = (
        float(data[1]),
        float(data[2]),
        float(data[3]),
    )

    p2 = (
        float(data[4]),
        float(data[5]),
        float(data[6]),
    )

    pi = math.pi

    # Distances from sphere center to scanners.
    d1 = norm(p1)
    d2 = norm(p2)

    # Angular radii of visible caps satisfy:
    # cos(a) = R / d1
    # cos(b) = R / d2
    ca = clamp_cos(R / d1)
    cb = clamp_cos(R / d2)

    a = math.acos(ca)
    b = math.acos(cb)

    sa = math.sqrt(max(0.0, 1.0 - ca * ca))
    sb = math.sqrt(max(0.0, 1.0 - cb * cb))

    # Angle between the two scanner directions.
    ct = dot(p1, p2) / (d1 * d2)
    ct = clamp_cos(ct)

    t = math.acos(ct)
    st = math.sqrt(max(0.0, 1.0 - ct * ct))

    # Area of each spherical cap.
    area1 = 2.0 * pi * R * R * (1.0 - ca)
    area2 = 2.0 * pi * R * R * (1.0 - cb)

    # Compute intersection area of the two caps.
    if t >= a + b - EPS:
        # Disjoint or tangent caps.
        intersection = 0.0

    elif t + min(a, b) <= max(a, b) + EPS:
        # One cap completely contains the other.
        intersection = min(area1, area2)

    else:
        # Partial overlap: spherical lens.

        # Half-span of the arc from cap 1 boundary.
        psi_a = math.acos(
            clamp_cos((cb - ca * ct) / (sa * st))
        )

        # Half-span of the arc from cap 2 boundary.
        psi_b = math.acos(
            clamp_cos((ca - cb * ct) / (sb * st))
        )

        # Angle between boundary tangent directions.
        gamma = math.acos(
            clamp_cos((ct - ca * cb) / (sa * sb))
        )

        # Lens area formula, scaled by R^2.
        intersection = R * R * (
            2.0 * (pi - gamma)
            - 2.0 * psi_a * ca
            - 2.0 * psi_b * cb
        )

        # Numerical safety.
        if -1e-9 < intersection < 0.0:
            intersection = 0.0

    # Union area by inclusion-exclusion.
    answer = area1 + area2 - intersection

    print(f"{answer:.3f}")


if __name__ == "__main__":
    main()
```