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

345. Revolution
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



During the last parliament elections in Berland two political parties collected the same amount of votes. Now the first party hired you to help them with their plan of a revolution.

During the revolution they want to split the country into two parts. The party is very democratic, so each member has its own separation plan.

The border of Berland can be considered as a convex polygon on the plane. The polygon can have three or more consecutive vertices lay on one line. Each separation plan is represented by the line of the cut.

Your program should calculate the area of the smallest part of the Berland for each separation plan.

Input
The first line of the input contains integer N (3 ≤ N ≤ 5 · 104). Next N lines contain coordinates xi, yi of the Berland border in the clockwise or counterclockwise order. The polygon is non-degenerate. The next line contains integer P (1 ≤ P ≤ 5 · 104). Next P lines contain coordinates x1,j, y1,j, x2,j, y2,j of two distinct points on the separation line. All coordinates are real and do not exceed 104 by the absolute value. They are given with no more than 4 significant digits after decimal point.

Output
Print P lines. Each line should contain the area of the smallest part after separating Berland with the corresponding line. Print value with at least 6 digits after decimal point. Absolute or relative error must be less than 10-5.

Example(s)
sample input
sample output
5
0 0
0 5
0 10
10 10
10 0
4
0 0 10 10
9 10 10 9
10 -1 12 11
10 10 0 5
50.000000
0.500000
0.000000
25.000000

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

Given a convex polygon with `N ≤ 5 · 10^4` vertices and `P ≤ 5 · 10^4` query lines, for each line compute the area of the smaller part of the polygon after cutting it by that line.

If the line does not split the polygon into two non-zero-area parts, output `0`.

The polygon vertices are given in clockwise or counterclockwise order, and consecutive collinear vertices may exist.

---

## 2. Key observations needed to solve the problem

### Observation 1: Signed side of a point

For a query line passing through points `a` and `b`, define:

```text
d = b - a
side(p) = d × (p - a)
```

where `×` is the 2D cross product.

Then:

- `side(p) > 0`: point is on the left side of the directed line `a → b`
- `side(p) < 0`: point is on the right side
- `side(p) = 0`: point lies on the line

For a convex polygon:

- if all vertices have `side >= 0`, the line does not properly cut the polygon;
- if all vertices have `side <= 0`, the line does not properly cut the polygon;
- otherwise, the line intersects the polygon boundary in two points and splits it.

So each query needs:

1. Determine if both positive and negative vertices exist.
2. Find the two crossed edges.
3. Compute the area on one side.
4. Return the smaller of that area and `total_area - area`.

---

### Observation 2: We cannot scan all vertices per query

A direct `O(N)` check per query would cost:

```text
O(NP) = 2.5 · 10^9
```

which is too large.

We need about `O(log N)` per query.

---

### Observation 3: Convex polygon chains are useful

After making the polygon counterclockwise, find:

- the lexicographically leftmost vertex,
- the lexicographically rightmost vertex.

These two vertices split the convex polygon into two convex monotone chains.

For any fixed query line, the values:

```text
side(vertex)
```

along each chain are unimodal. Therefore, maximum and minimum side values on each chain can be found by binary search.

This gives the global maximum and minimum side values in `O(log N)`.

---

### Observation 4: Crossed edges can be found by binary search

Let:

- `i_min` be a vertex with minimum `side`,
- `i_max` be a vertex with maximum `side`.

If:

```text
side(i_max) <= 0
```

or

```text
side(i_min) >= 0
```

then the polygon is not properly split.

Otherwise:

- along the counterclockwise arc from `i_min` to `i_max`, side values go from negative to positive;
- along the counterclockwise arc from `i_max` to `i_min`, side values go from positive to negative.

So the two crossing edges can also be found by binary search.

---

### Observation 5: Area can be computed using shoelace prefix sums

Precompute prefix sums of shoelace terms:

```text
pref[i + 1] = pref[i] + polygon[i] × polygon[i + 1]
```

Then the shoelace contribution of any consecutive boundary chain can be obtained in `O(1)`.

Once the two intersection points are known, the area of one side of the cut can be computed directly using the shoelace formula.

---

## 3. Full solution approach

### Preprocessing

1. Read the polygon.
2. Compute its signed doubled area.
3. If the area is negative, reverse the vertex order so the polygon becomes counterclockwise.
4. Compute prefix shoelace sums.
5. Find the lexicographically leftmost and rightmost vertices.
6. Split the polygon into two chains:
   - `leftmost → rightmost`
   - `rightmost → leftmost`
7. Duplicate the vertex array to simplify cyclic indexing.

---

### Query processing

For each query line through points `a` and `b`:

1. Let:

   ```text
   d = b - a
   side(i) = d × (polygon[i] - a)
   ```

2. Find the maximum side value:
   - maximum on first chain,
   - maximum on second chain,
   - take the larger.

3. Find the minimum side value:
   - minimum on first chain,
   - minimum on second chain,
   - take the smaller.

4. If there is no positive side or no negative side, output `0`.

5. Otherwise, binary search for:
   - first positive vertex on the arc from `i_min` to `i_max`,
   - last positive vertex on the arc from `i_max` to `i_min`.

6. These determine the two polygon edges crossed by the query line.

7. Compute the intersection points of those edges with the query line.

8. Compute the area of the positive-side polygon piece using the shoelace formula and prefix sums.

9. Output:

   ```text
   min(piece_area, total_area - piece_area)
   ```

---

### Complexity

Preprocessing:

```text
O(N)
```

Each query:

```text
O(log N)
```

Total:

```text
O(N + P log N)
```

Memory:

```text
O(N)
```

---

## 4. C++ implementation with detailed comments

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

using Real = double;

const Real EPS = 1e-9;

struct Point {
    Real x, y;

    Point() : x(0), y(0) {}
    Point(Real x_, Real y_) : x(x_), y(y_) {}

    Point operator + (const Point& other) const {
        return Point(x + other.x, y + other.y);
    }

    Point operator - (const Point& other) const {
        return Point(x - other.x, y - other.y);
    }

    Point operator * (Real k) const {
        return Point(x * k, y * k);
    }

    bool operator < (const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// 2D cross product.
Real cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

// Intersection of two infinite lines:
// first line: p1 -> p2
// second line: q1 -> q2
Point lineIntersection(const Point& p1, const Point& p2,
                       const Point& q1, const Point& q2) {
    Point d1 = p2 - p1;
    Point d2 = q2 - q1;

    Real t = cross(q1 - p1, d2) / cross(d1, d2);

    return p1 + d1 * t;
}

// Binary search for the first integer in [lo, hi)
// for which pred(index) is true.
template <class Predicate>
int firstTrue(int lo, int hi, Predicate pred) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (pred(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    return lo;
}

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

    int n;
    cin >> n;

    vector<Point> pts(n);

    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y;
    }

    // Compute doubled signed polygon area.
    Real area2 = 0;

    for (int i = 0; i < n; i++) {
        area2 += cross(pts[i], pts[(i + 1) % n]);
    }

    // Make polygon counterclockwise.
    if (area2 < 0) {
        reverse(pts.begin(), pts.end());
        area2 = -area2;
    }

    Real totalArea = area2 / 2.0;

    // Prefix sums of shoelace edge contributions.
    vector<Real> pref(n + 1, 0);

    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + cross(pts[i], pts[(i + 1) % n]);
    }

    // Find lexicographically leftmost and rightmost vertices.
    int leftIdx = 0;
    int rightIdx = 0;

    for (int i = 1; i < n; i++) {
        if (pts[i] < pts[leftIdx]) {
            leftIdx = i;
        }

        if (pts[rightIdx] < pts[i]) {
            rightIdx = i;
        }
    }

    // Chain lengths.
    // Chain 1: leftIdx -> rightIdx in CCW order.
    // Chain 2: rightIdx -> leftIdx in CCW order.
    int lowerLen = (rightIdx - leftIdx + n) % n + 1;
    int upperLen = (leftIdx - rightIdx + n) % n + 1;

    // Duplicate points to avoid modulo operations during binary searches.
    vector<Point> p2 = pts;

    for (int i = 0; i < n; i++) {
        p2.push_back(pts[i]);
    }

    int q;
    cin >> q;

    cout << fixed << setprecision(6);

    while (q--) {
        Point a, b;
        cin >> a.x >> a.y >> b.x >> b.y;

        Point d = b - a;

        // Signed side of vertex i relative to directed line a -> b.
        auto side = [&](int i) -> Real {
            return cross(d, p2[i] - a);
        };

        // Finds maximum or minimum side value on one convex chain.
        auto extremeOnChain = [&](int start, int len, bool wantMax) -> int {
            int lo = 0;
            int hi = len - 1;

            // Binary search on a unimodal sequence.
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;

                Real cur = side(start + mid);
                Real nxt = side(start + mid + 1);

                if (wantMax) {
                    // Move right while values are increasing.
                    if (cur < nxt) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                } else {
                    // Move right while values are decreasing.
                    if (cur > nxt) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
            }

            int best = lo;
            Real bestValue = side(start + best);

            // Depending on the chain shape, the requested extreme may be
            // at an endpoint, so check endpoints explicitly.
            Real firstValue = side(start);

            if (wantMax) {
                if (firstValue > bestValue) {
                    best = 0;
                    bestValue = firstValue;
                }
            } else {
                if (firstValue < bestValue) {
                    best = 0;
                    bestValue = firstValue;
                }
            }

            Real lastValue = side(start + len - 1);

            if (wantMax) {
                if (lastValue > bestValue) {
                    best = len - 1;
                }
            } else {
                if (lastValue < bestValue) {
                    best = len - 1;
                }
            }

            return best;
        };

        // Find global maximum side vertex.
        int maxLower = extremeOnChain(leftIdx, lowerLen, true);
        int maxUpper = extremeOnChain(rightIdx, upperLen, true);

        Real maxLowerValue = side(leftIdx + maxLower);
        Real maxUpperValue = side(rightIdx + maxUpper);

        int iMax;

        if (maxLowerValue >= maxUpperValue) {
            iMax = (leftIdx + maxLower) % n;
        } else {
            iMax = (rightIdx + maxUpper) % n;
        }

        // No positive vertex means the line does not cut the polygon.
        if (side(iMax) <= EPS) {
            cout << 0.0 << '\n';
            continue;
        }

        // Find global minimum side vertex.
        int minLower = extremeOnChain(leftIdx, lowerLen, false);
        int minUpper = extremeOnChain(rightIdx, upperLen, false);

        Real minLowerValue = side(leftIdx + minLower);
        Real minUpperValue = side(rightIdx + minUpper);

        int iMin;

        if (minLowerValue <= minUpperValue) {
            iMin = (leftIdx + minLower) % n;
        } else {
            iMin = (rightIdx + minUpper) % n;
        }

        // No negative vertex means the line does not cut the polygon.
        if (side(iMin) >= -EPS) {
            cout << 0.0 << '\n';
            continue;
        }

        // Distance along CCW arcs.
        int lenUp = (iMax - iMin + n) % n;
        int lenDown = (iMin - iMax + n) % n;

        // On arc iMin -> iMax, find first positive vertex.
        int firstPositiveOffset = firstTrue(1, lenUp + 1, [&](int k) {
            return side(iMin + k) > 0;
        });

        // On arc iMax -> iMin, find where positive vertices end.
        int lastPositiveOffset = firstTrue(1, lenDown, [&](int k) {
            return side(iMax + k) <= 0;
        }) - 1;

        auto wrap = [&](int idx) {
            return idx < n ? idx : idx - n;
        };

        int firstPositive = wrap(iMin + firstPositiveOffset);
        int lastPositive = wrap(iMax + lastPositiveOffset);

        int beforeFirst = firstPositive == 0 ? n - 1 : firstPositive - 1;
        int afterLast = lastPositive + 1 == n ? 0 : lastPositive + 1;

        // Two intersection points with polygon boundary.
        Point x = lineIntersection(pts[beforeFirst], pts[firstPositive], a, b);
        Point y = lineIntersection(pts[lastPositive], pts[afterLast], a, b);

        // Shoelace contribution of polygon chain:
        // firstPositive -> ... -> lastPositive.
        Real chainSum;

        if (firstPositive <= lastPositive) {
            chainSum = pref[lastPositive] - pref[firstPositive];
        } else {
            chainSum = pref[n] - pref[firstPositive] + pref[lastPositive];
        }

        // Doubled area of the positive-side piece:
        //
        // x -> firstPositive -> ... -> lastPositive -> y -> x
        Real pieceArea2 =
            cross(x, pts[firstPositive])
            + chainSum
            + cross(pts[lastPositive], y)
            + cross(y, x);

        Real pieceArea = fabs(pieceArea2) / 2.0;

        Real answer = min(pieceArea, totalArea - pieceArea);

        // Clamp small negative values caused by floating-point error.
        if (answer < 0 && answer > -1e-7) {
            answer = 0;
        }

        cout << answer << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys

EPS = 1e-9


def cross(a, b):
    """
    2D cross product.
    """
    return a[0] * b[1] - a[1] * b[0]


def sub(a, b):
    """
    Vector subtraction a - b.
    """
    return (a[0] - b[0], a[1] - b[1])


def first_true(lo, hi, pred):
    """
    Binary search for the first integer x in [lo, hi)
    such that pred(x) is True.

    Assumes the predicate is monotone:
    False, False, ..., True, True.
    """
    while lo < hi:
        mid = (lo + hi) // 2

        if pred(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo


def line_intersection(p1, p2, q1, q2):
    """
    Intersection of two infinite lines:
    line p1 -> p2 and line q1 -> q2.
    """
    d1 = sub(p2, p1)
    d2 = sub(q2, q1)

    t = cross(sub(q1, p1), d2) / cross(d1, d2)

    return (
        p1[0] + d1[0] * t,
        p1[1] + d1[1] * t,
    )


def solve():
    data = sys.stdin.buffer.read().split()
    ptr = 0

    n = int(data[ptr])
    ptr += 1

    pts = []

    for _ in range(n):
        x = float(data[ptr])
        y = float(data[ptr + 1])
        ptr += 2
        pts.append((x, y))

    # Compute doubled signed polygon area.
    area2 = 0.0

    for i in range(n):
        area2 += cross(pts[i], pts[(i + 1) % n])

    # Make polygon counterclockwise.
    if area2 < 0:
        pts.reverse()
        area2 = -area2

    total_area = area2 / 2.0

    # Prefix sums of shoelace edge contributions.
    pref = [0.0] * (n + 1)

    for i in range(n):
        pref[i + 1] = pref[i] + cross(pts[i], pts[(i + 1) % n])

    # Find lexicographically leftmost and rightmost vertices.
    left_idx = 0
    right_idx = 0

    for i in range(1, n):
        if pts[i] < pts[left_idx]:
            left_idx = i

        if pts[right_idx] < pts[i]:
            right_idx = i

    # Chain lengths.
    lower_len = (right_idx - left_idx) % n + 1
    upper_len = (left_idx - right_idx) % n + 1

    # Duplicate array for easier cyclic indexing.
    pts2 = pts + pts

    q = int(data[ptr])
    ptr += 1

    out = []

    for _ in range(q):
        ax = float(data[ptr])
        ay = float(data[ptr + 1])
        bx = float(data[ptr + 2])
        by = float(data[ptr + 3])
        ptr += 4

        a = (ax, ay)
        b = (bx, by)
        d = (bx - ax, by - ay)

        def side(i):
            """
            Signed side of vertex i relative to directed query line a -> b.
            """
            p = pts2[i]
            return cross(d, (p[0] - ax, p[1] - ay))

        def extreme_on_chain(start, length, want_max):
            """
            Finds maximum or minimum side value on one convex chain.

            Because side values on a convex chain are unimodal,
            binary search on adjacent values is sufficient.
            """
            lo = 0
            hi = length - 1

            while lo < hi:
                mid = (lo + hi) // 2

                cur = side(start + mid)
                nxt = side(start + mid + 1)

                if want_max:
                    if cur < nxt:
                        lo = mid + 1
                    else:
                        hi = mid
                else:
                    if cur > nxt:
                        lo = mid + 1
                    else:
                        hi = mid

            best = lo
            best_value = side(start + best)

            # The required extreme may be at an endpoint.
            first_value = side(start)

            if want_max:
                if first_value > best_value:
                    best = 0
                    best_value = first_value
            else:
                if first_value < best_value:
                    best = 0
                    best_value = first_value

            last_value = side(start + length - 1)

            if want_max:
                if last_value > best_value:
                    best = length - 1
            else:
                if last_value < best_value:
                    best = length - 1

            return best

        # Global maximum side vertex.
        max_lower = extreme_on_chain(left_idx, lower_len, True)
        max_upper = extreme_on_chain(right_idx, upper_len, True)

        max_lower_value = side(left_idx + max_lower)
        max_upper_value = side(right_idx + max_upper)

        if max_lower_value >= max_upper_value:
            i_max = (left_idx + max_lower) % n
        else:
            i_max = (right_idx + max_upper) % n

        # No positive vertex: no proper split.
        if side(i_max) <= EPS:
            out.append("0.000000")
            continue

        # Global minimum side vertex.
        min_lower = extreme_on_chain(left_idx, lower_len, False)
        min_upper = extreme_on_chain(right_idx, upper_len, False)

        min_lower_value = side(left_idx + min_lower)
        min_upper_value = side(right_idx + min_upper)

        if min_lower_value <= min_upper_value:
            i_min = (left_idx + min_lower) % n
        else:
            i_min = (right_idx + min_upper) % n

        # No negative vertex: no proper split.
        if side(i_min) >= -EPS:
            out.append("0.000000")
            continue

        # Counterclockwise arc lengths.
        len_up = (i_max - i_min) % n
        len_down = (i_min - i_max) % n

        # Arc i_min -> i_max:
        # find first positive vertex.
        first_positive_offset = first_true(
            1,
            len_up + 1,
            lambda k: side(i_min + k) > 0
        )

        # Arc i_max -> i_min:
        # find where positive vertices end.
        last_positive_offset = first_true(
            1,
            len_down,
            lambda k: side(i_max + k) <= 0
        ) - 1

        def wrap(idx):
            return idx if idx < n else idx - n

        first_positive = wrap(i_min + first_positive_offset)
        last_positive = wrap(i_max + last_positive_offset)

        before_first = n - 1 if first_positive == 0 else first_positive - 1
        after_last = 0 if last_positive + 1 == n else last_positive + 1

        # Boundary intersections with the cutting line.
        x = line_intersection(
            pts[before_first],
            pts[first_positive],
            a,
            b
        )

        y = line_intersection(
            pts[last_positive],
            pts[after_last],
            a,
            b
        )

        # Shoelace contribution of polygon chain:
        # first_positive -> ... -> last_positive.
        if first_positive <= last_positive:
            chain_sum = pref[last_positive] - pref[first_positive]
        else:
            chain_sum = pref[n] - pref[first_positive] + pref[last_positive]

        # Doubled area of the positive-side piece:
        #
        # x -> first_positive -> ... -> last_positive -> y -> x
        piece_area2 = (
            cross(x, pts[first_positive])
            + chain_sum
            + cross(pts[last_positive], y)
            + cross(y, x)
        )

        piece_area = abs(piece_area2) / 2.0

        answer = min(piece_area, total_area - piece_area)

        # Clamp tiny floating-point errors.
        if answer < 0 and answer > -1e-7:
            answer = 0.0

        out.append(f"{answer:.6f}")

    sys.stdout.write("\n".join(out))


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

The C++ version is the intended efficient implementation for the given constraints. The Python version follows the same algorithm and is useful for understanding or environments with a more relaxed time limit.