<|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.

408. Game with points
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

Recently Petya has discovered new game with points. Rules of the game are quite simple. First, there is only one point A0 with coordinates (0, 0). Then Petya have to draw N another points. Points must be drawn consequently and each new point must be connected with exactly one of the previous points by a segment. Let's decribe the game process more formally. At the i-th step Petya chooses the position of the point Ai (not necessarily with integer coordinates). Than he chooses one of the previously drawn points in order to connect it with the point Ai. Lets call this point B. The following conditions must be held:
Point Ai must not coincide with any of the previous points.
Point Ai must not lie on the previously drawn segments.
Segment AiB must not have common points with previously drawn segments, except possibly the point B.
Segment AiB must not cover any of the previous points, except the point B.
Length of the segment AiB must not exceed 1. After drawing each point Petya computes two values.
The largest number of segments which share a common point.
The largest euclid distance between some pair of points. After each step Petya gains the score which is equal to the product of these values. Find out which is the maximal score Petya can gain after the whole game.
Input
Input contains single integer number N (0 ≤ N ≤ 1000).
Output
Output the maximal score that Petya can gain. Your answer must be accurate up to 10-3.
Example(s)
sample input
sample output
2
5.000

sample input
sample output
4
20.000

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

We start with point \(A_0=(0,0)\). Then we add \(N\) new points one by one. Each new point is connected to exactly one previous point by a segment of length at most \(1\), and segments may not intersect or pass through previous points except at the chosen endpoint.

After each step, Petya gets:

\[
(\text{maximum number of segments sharing one point}) \times (\text{maximum Euclidean distance between two points})
\]

Find the maximum possible total score after all \(N\) points are added.

Constraints:

\[
0 \le N \le 1000
\]

Output the answer with accuracy \(10^{-3}\).

---

## 2. Key observations needed to solve the problem

### Observation 1: The drawing is always a tree

Every new point is connected to exactly one previous point. Therefore, after adding \(k\) points, we have:

- \(k+1\) vertices,
- \(k\) segments,
- no cycles.

So the structure is a tree embedded in the plane.

Because intersections are forbidden, the largest number of segments sharing a common point is just the maximum degree of this tree.

---

### Observation 2: For fixed number of edges and maximum degree, we can bound the diameter

Suppose after adding \(k\) points, the tree has \(k\) edges and maximum degree \(d\).

Take a vertex with degree \(d\). Any simple path in a tree can use at most two edges incident to this vertex. Therefore, at least \(d-2\) of its incident edges cannot belong to a diameter path.

So the number of edges on any diameter path is at most:

\[
k-(d-2)=k-d+2
\]

Since every segment has length at most \(1\), the Euclidean distance between two points is also at most the number of edges on the path between them.

Therefore, for \(d \ge 2\):

\[
\text{maximum possible distance} \le k-d+2
\]

---

### Observation 3: This bound is achievable

We can build the following shape:

- Choose one central vertex.
- Create \(d\) arms from it.
- Two arms are long and placed in opposite directions.
- The remaining \(d-2\) arms are single-edge leaves.

Then:

- maximum degree is \(d\),
- total number of edges is \(k\),
- the distance between the endpoints of the two long opposite arms is exactly:

\[
k-d+2
\]

So for fixed \(k\) and \(d\), the best score at step \(k\) is:

\[
d(k-d+2)
\]

For the special case \(k=1,d=1\), the score is \(1\).

---

### Observation 4: The maximum degree changes slowly

When adding one new point:

- the maximum degree can stay the same,
- or it can increase by exactly \(1\).

It can never decrease, and it cannot increase by more than \(1\) in one step.

This suggests dynamic programming over:

- number of added points,
- current maximum degree.

---

## 3. Full solution approach based on the observations

Define:

\[
dp[k][d]
\]

as the maximum total score after adding exactly \(k\) points, with current maximum degree equal to \(d\).

Base case:

\[
dp[1][1]=1
\]

because after adding one point:

- there is one segment,
- maximum degree is \(1\),
- maximum distance is \(1\),
- score is \(1\).

If \(N=0\), the answer is \(0\).

---

For \(k \ge 2\), a tree with \(k\) edges must have maximum degree at least \(2\), so we only consider:

\[
2 \le d \le k
\]

The score gained at step \(k\) with maximum degree \(d\) is:

\[
score(k,d)=d(k-d+2)
\]

There are two possible transitions.

---

### Transition 1: Maximum degree stays the same

We extend one of the existing long arms.

\[
dp[k][d] = \max(dp[k][d], dp[k-1][d] + score(k,d))
\]

---

### Transition 2: Maximum degree increases by one

We add a new arm from the central vertex.

\[
dp[k][d] = \max(dp[k][d], dp[k-1][d-1] + score(k,d))
\]

---

The answer is:

\[
\max_{d} dp[N][d]
\]

---

### Complexity

There are \(O(N^2)\) states and each state has \(O(1)\) transitions.

Time complexity:

\[
O(N^2)
\]

Memory complexity:

\[
O(N^2)
\]

For \(N \le 1000\), this easily fits.

---

## 4. C++ implementation with detailed comments

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

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

    int n;
    cin >> n;

    // If no points are added, no score is obtained.
    if (n == 0) {
        cout << fixed << setprecision(3) << 0.0 << '\n';
        return 0;
    }

    /*
        dp[k][d] = maximum total score after adding exactly k points
                   and having maximum degree exactly d.

        k ranges from 0 to n.
        d ranges from 0 to n.

        We use a very negative value for impossible states.
    */
    const double NEG_INF = -1e100;
    vector<vector<double>> dp(n + 1, vector<double>(n + 2, NEG_INF));

    /*
        Base case:
        After adding the first point:
        - there is exactly one edge,
        - maximum degree is 1,
        - diameter is 1,
        - score is 1.
    */
    dp[1][1] = 1.0;

    /*
        Fill DP table.

        For k >= 2, the maximum degree cannot be 1 anymore,
        because any connected tree with at least 2 edges has some vertex
        of degree at least 2.
    */
    for (int k = 2; k <= n; ++k) {
        for (int d = 2; d <= k; ++d) {
            /*
                For k edges and maximum degree d, the largest possible
                Euclidean distance is k - d + 2.

                Therefore the score at this step is:
                    maximum_degree * maximum_distance
                  = d * (k - d + 2)
            */
            double dist = k - d + 2;
            double score = d * dist;

            /*
                Transition 1:
                The previous maximum degree was also d.

                Geometrically, this corresponds to extending one of the
                two long arms.
            */
            if (d <= k - 1 && dp[k - 1][d] > NEG_INF / 2) {
                dp[k][d] = max(dp[k][d], dp[k - 1][d] + score);
            }

            /*
                Transition 2:
                The previous maximum degree was d - 1.

                Geometrically, this corresponds to adding a new arm
                from the central vertex.
            */
            if (dp[k - 1][d - 1] > NEG_INF / 2) {
                dp[k][d] = max(dp[k][d], dp[k - 1][d - 1] + score);
            }
        }
    }

    // Find the best possible final maximum degree.
    double ans = NEG_INF;
    for (int d = 1; d <= n; ++d) {
        ans = max(ans, dp[n][d]);
    }

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

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys

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

    n = int(data)

    # If no points are added, the total score is zero.
    if n == 0:
        print("0.000")
        return

    NEG_INF = -10**100

    # dp[k][d] = maximum total score after adding k points
    #            with maximum degree exactly d.
    dp = [[NEG_INF] * (n + 2) for _ in range(n + 1)]

    # Base case:
    # After adding one point:
    # - one segment exists,
    # - maximum degree is 1,
    # - maximum distance is 1,
    # - score is 1.
    dp[1][1] = 1.0

    # Fill the DP table.
    for k in range(2, n + 1):

        # For k >= 2, maximum degree must be at least 2.
        # It also cannot exceed k, because there are only k edges.
        for d in range(2, k + 1):

            # Maximum possible distance for k edges and degree d.
            dist = k - d + 2

            # Score gained at this step.
            score = d * dist

            # Transition 1:
            # The maximum degree was already d.
            # This means we extended an existing arm.
            if d <= k - 1 and dp[k - 1][d] > NEG_INF // 2:
                dp[k][d] = max(dp[k][d], dp[k - 1][d] + score)

            # Transition 2:
            # The maximum degree increased from d - 1 to d.
            # This means we added a new arm.
            if dp[k - 1][d - 1] > NEG_INF // 2:
                dp[k][d] = max(dp[k][d], dp[k - 1][d - 1] + score)

    # The final maximum degree can be anything from 1 to n.
    ans = max(dp[n][1:n + 1])

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


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