## 1. Abridged problem statement

Given a convex polygon with `N ≤ 5·10^4` vertices, and `P ≤ 5·10^4` query lines, each line representing a possible cut of the polygon, compute for every query the area of the smaller of the two parts into which the line divides the polygon.

If the line does not properly split the polygon, the answer is `0`.

The polygon vertices are given in clockwise or counterclockwise order. Consecutive collinear vertices may exist. Coordinates are real numbers.

Output each answer with at least 6 digits after the decimal point.

---

## 2. Detailed Editorial

### Key geometric idea

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.

`side(p)` tells on which side of the directed line `a → b` the point `p` lies:

- `side(p) > 0`: left side,
- `side(p) < 0`: right side,
- `side(p) = 0`: on the line.

For a convex polygon:

- if all vertices have non-positive signed side, the line does not cut the polygon;
- if all vertices have non-negative signed side, the line does not cut the polygon;
- otherwise, the line intersects the polygon in exactly two boundary points and splits it into two convex pieces.

So for each query we need:

1. Find whether both positive and negative vertices exist.
2. Find the two polygon edges crossed by the line.
3. Compute the area of one side.
4. Return the smaller of that area and `total_area - area`.

---

### Why not scan all vertices per query?

`N` and `P` can both be `5·10^4`, so an `O(NP)` solution is impossible.

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

---

### Preprocessing

First, ensure the polygon is stored counterclockwise.

The signed doubled area of the polygon is:

```text
sum += pts[i] ^ pts[(i + 1) % n]
```

If this value is negative, the vertices are clockwise, so reverse them.

Then compute prefix sums of shoelace terms:

```text
pref[i + 1] = pref[i] + pts[i] ^ pts[(i + 1) % n]
```

This lets us get the doubled area contribution of any consecutive boundary chain in `O(1)`.

---

### Splitting the polygon into two monotone chains

Find:

- `l_idx`: lexicographically leftmost vertex,
- `r_idx`: lexicographically rightmost vertex.

Because the polygon is convex, the boundary from `l_idx` to `r_idx` and the boundary from `r_idx` back to `l_idx` form two convex monotone chains.

The code calls them:

```text
lower chain = l_idx → r_idx
upper chain = r_idx → l_idx
```

The point array is duplicated so cyclic ranges can be accessed linearly.

---

### Finding maximum and minimum side values

For a fixed query line, `side(vertex)` is a linear function over the polygon.

On each convex chain, this sequence is unimodal: it has at most one local maximum or one local minimum.

Therefore, on each chain we can find:

- the maximum signed side,
- the minimum signed side,

using binary search on the slope direction.

Then the global maximum is the larger of the two chain maxima, and the global minimum is the smaller of the two chain minima.

If:

```text
max_side <= 0
```

or

```text
min_side >= 0
```

then the polygon lies on one side of the line, so the answer is `0`.

---

### Finding the two intersection edges

Let:

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

Since the polygon is convex:

- going counterclockwise from `i_min` to `i_max`, side values increase from negative to positive;
- going counterclockwise from `i_max` to `i_min`, side values decrease from positive to negative.

Therefore:

1. On the arc from `i_min` to `i_max`, binary search the first vertex with `side > 0`.
2. On the arc from `i_max` to `i_min`, binary search the first vertex with `side <= 0`; the previous vertex is the last positive vertex.

These identify the two polygon edges crossed by the query line.

---

### Computing the area of the positive-side polygon piece

Suppose the positive side consists of:

```text
x → ccw_first → ... → ccw_last → y → x
```

where:

- `x` is the first intersection point,
- `y` is the second intersection point,
- `ccw_first ... ccw_last` are polygon vertices lying on the positive side.

The doubled area is computed by shoelace formula:

```text
doubled =
    x ^ pts[ccw_first]
  + chain_sum
  + pts[ccw_last] ^ y
  + y ^ x
```

The chain sum is obtained from prefix sums.

Then:

```text
piece = abs(doubled) / 2
answer = min(piece, total_area - piece)
```

Small negative values caused by floating point error are clamped to zero.

---

### Complexity

Preprocessing:

```text
O(N)
```

Each query:

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

Total:

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

Memory:

```text
O(N)
```

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;
    static inline const coord_t PI = acos((coord_t)-1.0);

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }

    friend coord_t arc_area(
        const Point& center, coord_t r, const Point& p1, const Point& p2
    ) {
        coord_t theta1 = (p1 - center).angle();
        coord_t theta2 = (p2 - center).angle();
        if(theta2 < theta1 - eps) {
            theta2 += 2 * PI;
        }

        coord_t d_theta = theta2 - theta1;
        coord_t cx = center.x, cy = center.y;
        coord_t area = r * cx * (sin(theta2) - sin(theta1)) -
                       r * cy * (cos(theta2) - cos(theta1)) + r * r * d_theta;
        return area / 2.0;
    }

    friend vector<Point> intersect_circles(
        const Point& c1, coord_t r1, const Point& c2, coord_t r2
    ) {
        Point d = c2 - c1;
        coord_t dist = d.norm();

        if(dist > r1 + r2 + eps || dist < abs(r1 - r2) - eps || dist < eps) {
            return {};
        }

        coord_t a = (r1 * r1 - r2 * r2 + dist * dist) / (2 * dist);
        coord_t h_sq = r1 * r1 - a * a;
        if(h_sq < -eps) {
            return {};
        }
        if(h_sq < 0) {
            h_sq = 0;
        }
        coord_t h = sqrt(h_sq);

        Point mid = c1 + d.unit() * a;
        Point perp_dir = d.perp().unit();

        if(h < eps) {
            return {mid};
        }
        return {mid + perp_dir * h, mid - perp_dir * h};
    }

    friend optional<Point> intersect_ray_segment(
        const Point& ray_start, const Point& ray_through, const Point& seg_a,
        const Point& seg_b
    ) {
        Point ray_dir = ray_through - ray_start;
        if(ray_dir.norm2() < Point::eps) {
            return {};
        }
        Point seg_dir = seg_b - seg_a;
        coord_t denom = ray_dir ^ seg_dir;
        if(fabs(denom) < eps) {
            return {};
        }
        coord_t t = ((seg_a - ray_start) ^ seg_dir) / denom;
        if(t < eps) {
            return {};
        }
        coord_t s = ((seg_a - ray_start) ^ ray_dir) / denom;
        if(s < eps || s > 1 - eps) {
            return {};
        }
        return ray_start + ray_dir * t;
    }
};

template<typename F>
int first_true(int lo, int hi, F pred) {
    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if(pred(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

char in_buf[1 << 16];
int in_pos = 0, in_len = 0;

int next_char() {
    if(in_pos == in_len) {
        in_len = (int)fread(in_buf, 1, sizeof(in_buf), stdin);
        in_pos = 0;
        if(in_len == 0) {
            return -1;
        }
    }
    return in_buf[in_pos++];
}

int read_int() {
    int c = next_char();
    while(c <= ' ') {
        c = next_char();
    }
    bool neg = c == '-';
    if(neg) {
        c = next_char();
    }
    int x = 0;
    while(c > ' ') {
        x = x * 10 + (c - '0');
        c = next_char();
    }
    return neg ? -x : x;
}

coord_t read_real() {
    int c = next_char();
    while(c <= ' ') {
        c = next_char();
    }
    int sign = 1;
    if(c == '-') {
        sign = -1;
        c = next_char();
    } else if(c == '+') {
        c = next_char();
    }

    int64_t ival = 0;
    while(c >= '0' && c <= '9') {
        ival = ival * 10 + (c - '0');
        c = next_char();
    }

    coord_t val = (coord_t)ival;
    if(c == '.') {
        c = next_char();
        int64_t fval = 0;
        int fdigits = 0;
        while(c >= '0' && c <= '9' && fdigits < 18) {
            fval = fval * 10 + (c - '0');
            fdigits++;
            c = next_char();
        }

        while(c >= '0' && c <= '9') {
            c = next_char();
        }

        if(fdigits > 0) {
            static const coord_t ipow10[19] = {1.0,   1e-1,  1e-2,  1e-3,
                                               1e-4,  1e-5,  1e-6,  1e-7,
                                               1e-8,  1e-9,  1e-10, 1e-11,
                                               1e-12, 1e-13, 1e-14, 1e-15,
                                               1e-16, 1e-17, 1e-18};
            val += (coord_t)fval * ipow10[fdigits];
        }
    }
    return sign * val;
}

int n, q;
vector<Point> pts;
vector<coord_t> pref;
coord_t total_area;
int l_idx, r_idx;
int lower_len, upper_len;

void read() {
    n = read_int();
    pts.resize(n);
    for(int i = 0; i < n; i++) {
        pts[i].x = read_real();
        pts[i].y = read_real();
    }

    coord_t s = 0;
    for(int i = 0; i < n; i++) {
        s += pts[i] ^ pts[(i + 1) % n];
    }

    if(s < 0) {
        reverse(pts.begin(), pts.end());
        s = -s;
    }

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

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

    lower_len = ((r_idx - l_idx) % n + n) % n + 1;
    upper_len = ((l_idx - r_idx) % n + n) % n + 1;

    pts.resize(2 * n);
    for(int i = 0; i < n; i++) {
        pts[n + i] = pts[i];
    }

    total_area = s / 2;
    q = read_int();
}

void solve() {
    // After ensuring CCW orientation we precompute prefix shoelace sums
    // and split the polygon into two x-monotone chains by the leftmost
    // and rightmost vertices l_idx and r_idx:
    //
    //   lower chain = pts[l_idx], pts[l_idx + 1], ..., pts[r_idx]
    //   upper chain = pts[r_idx], pts[r_idx + 1], ..., pts[l_idx]
    //
    // Both chains share l_idx and r_idx. They are individually convex,
    // so for any cut line with direction d the side function
    // side(i) = d ^ (pts[i] - a) is unimodal on each chain: convex (one
    // interior minimum, max at endpoint) when d.x has the appropriate
    // sign for that chain, concave (one interior maximum, min at
    // endpoint) otherwise. This means a single ternary search per chain
    // suffices to find both extrema, and the polygon-wide peak i_max
    // and trough i_min are just the max/min across the two chains.
    //
    // Once i_max and i_min are known, side is genuinely monotone on each
    // arc between them: ascending on the arc from i_min to i_max (CCW),
    // descending on the arc from i_max to i_min (CCW). A textbook binary
    // search on each arc locates the zero crossing, giving the two edges
    // the cut intersects. The line_line_intersection of d with each of
    // those edges yields x and y, and the positive piece's doubled area
    // is the shoelace sum (x ^ pts[ccw_first]) + chain_sum + (pts[ccw_last]
    // ^ y) + (y ^ x), where chain_sum reduces to a prefix-sum slice.
    // The answer is min(piece, total - piece).

    cout << fixed << setprecision(6);

    for(int qi = 0; qi < q; qi++) {
        Point a, b;
        a.x = read_real();
        a.y = read_real();
        b.x = read_real();
        b.y = read_real();
        Point d = b - a;

        auto side = [&](int i) -> coord_t { return d ^ (pts[i] - a); };

        auto extreme_on_chain = [&](int chain_start, int chain_len,
                                    bool want_max) -> int {
            int lo = 0, hi = chain_len - 1;
            while(lo < hi) {
                int mid = lo + (hi - lo) / 2;
                coord_t sm = side(chain_start + mid);
                coord_t sn = side(chain_start + mid + 1);
                if(want_max ? sm < sn : sm > sn) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            int best = lo;
            coord_t best_v = side(chain_start + lo);
            coord_t v0 = side(chain_start);
            if(want_max ? v0 > best_v : v0 < best_v) {
                best = 0;
                best_v = v0;
            }
            coord_t vL = side(chain_start + chain_len - 1);
            if(want_max ? vL > best_v : vL < best_v) {
                best = chain_len - 1;
            }
            return best;
        };

        int max_lower_k = extreme_on_chain(l_idx, lower_len, true);
        int max_upper_k = extreme_on_chain(r_idx, upper_len, true);
        coord_t max_lower_v = side(l_idx + max_lower_k);
        coord_t max_upper_v = side(r_idx + max_upper_k);
        int i_max = max_lower_v >= max_upper_v ? (l_idx + max_lower_k) % n
                                               : (r_idx + max_upper_k) % n;

        if(side(i_max) <= Point::eps) {
            cout << (coord_t)0 << '\n';
            continue;
        }

        int min_lower_k = extreme_on_chain(l_idx, lower_len, false);
        int min_upper_k = extreme_on_chain(r_idx, upper_len, false);
        coord_t min_lower_v = side(l_idx + min_lower_k);
        coord_t min_upper_v = side(r_idx + min_upper_k);
        int i_min = min_lower_v <= min_upper_v ? (l_idx + min_lower_k) % n
                                               : (r_idx + min_upper_k) % n;

        if(side(i_min) >= -Point::eps) {
            cout << (coord_t)0 << '\n';
            continue;
        }

        int len_up = ((i_max - i_min) % n + n) % n;
        int len_dn = ((i_min - i_max) % n + n) % n;

        int ccw_first_k = first_true(1, len_up + 1, [&](int k) {
            return side(i_min + k) > 0;
        });
        int ccw_last_k =
            first_true(1, len_dn, [&](int k) { return side(i_max + k) <= 0; }) -
            1;

        auto wrap = [&](int i) { return i < n ? i : i - n; };
        int ccw_first = wrap(i_min + ccw_first_k);
        int ccw_last = wrap(i_max + ccw_last_k);
        int prev_f = ccw_first == 0 ? n - 1 : ccw_first - 1;
        int next_l = ccw_last + 1 == n ? 0 : ccw_last + 1;

        Point x = line_line_intersection(pts[prev_f], pts[ccw_first], a, b);
        Point y = line_line_intersection(pts[ccw_last], pts[next_l], a, b);

        coord_t chain = ccw_first <= ccw_last
                            ? pref[ccw_last] - pref[ccw_first]
                            : pref[n] - pref[ccw_first] + pref[ccw_last];
        coord_t doubled =
            (x ^ pts[ccw_first]) + chain + (pts[ccw_last] ^ y) + (y ^ x);
        coord_t piece = fabs(doubled) / 2;
        cout << max(min(piece, total_area - piece), (coord_t)0) << '\n';
    }
}

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

    int T = 1;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python solution

```python
import sys
import math


EPS = 1e-9


def cross(p, q):
    """
    Returns the 2D cross product p ^ q.
    """
    return p[0] * q[1] - p[1] * q[0]


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

    Assumes pred 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, a, d):
    """
    Intersects the infinite line p1-p2 with the query line a + t*d.

    p1, p2: endpoints of a polygon edge.
    a: one point on the query line.
    d: direction vector of the query line.
    """
    edge = (p2[0] - p1[0], p2[1] - p1[1])

    numerator = cross((a[0] - p1[0], a[1] - p1[1]), d)
    denominator = cross(edge, d)

    t = numerator / denominator

    return (
        p1[0] + edge[0] * t,
        p1[1] + edge[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 terms.
    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.
    l_idx = 0
    r_idx = 0

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

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

    # Chain from leftmost to rightmost.
    lower_len = (r_idx - l_idx) % n + 1

    # Chain from rightmost to leftmost.
    upper_len = (l_idx - r_idx) % n + 1

    # Duplicate points for easy 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)
        d = (bx - ax, by - ay)

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

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

            Because the side values along a convex chain are unimodal,
            binary search on neighboring values is enough.
            """
            lo = 0
            hi = length - 1

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

                sm = side(start + mid)
                sn = side(start + mid + 1)

                if want_max:
                    if sm < sn:
                        lo = mid + 1
                    else:
                        hi = mid
                else:
                    if sm > sn:
                        lo = mid + 1
                    else:
                        hi = mid

            best = lo
            best_val = side(start + best)

            # Check left endpoint.
            v0 = side(start)

            if want_max:
                if v0 > best_val:
                    best = 0
                    best_val = v0
            else:
                if v0 < best_val:
                    best = 0
                    best_val = v0

            # Check right endpoint.
            v_last = side(start + length - 1)

            if want_max:
                if v_last > best_val:
                    best = length - 1
            else:
                if v_last < best_val:
                    best = length - 1

            return best

        # Global maximum side vertex.
        max_lower_k = extreme_on_chain(l_idx, lower_len, True)
        max_upper_k = extreme_on_chain(r_idx, upper_len, True)

        max_lower_v = side(l_idx + max_lower_k)
        max_upper_v = side(r_idx + max_upper_k)

        if max_lower_v >= max_upper_v:
            i_max = (l_idx + max_lower_k) % n
        else:
            i_max = (r_idx + max_upper_k) % n

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

        # Global minimum side vertex.
        min_lower_k = extreme_on_chain(l_idx, lower_len, False)
        min_upper_k = extreme_on_chain(r_idx, upper_len, False)

        min_lower_v = side(l_idx + min_lower_k)
        min_upper_v = side(r_idx + min_upper_k)

        if min_lower_v <= min_upper_v:
            i_min = (l_idx + min_lower_k) % n
        else:
            i_min = (r_idx + min_upper_k) % n

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

        # Counterclockwise distance from i_min to i_max.
        len_up = (i_max - i_min) % n

        # Counterclockwise distance from i_max to i_min.
        len_dn = (i_min - i_max) % n

        # First positive vertex from i_min to i_max.
        ccw_first_k = first_true(
            1,
            len_up + 1,
            lambda k: side(i_min + k) > 0
        )

        # Last positive vertex from i_max toward i_min.
        ccw_last_k = first_true(
            1,
            len_dn,
            lambda k: side(i_max + k) <= 0
        ) - 1

        def wrap(i):
            """
            Converts an index in the duplicated array back to [0, n).
            """
            return i if i < n else i - n

        ccw_first = wrap(i_min + ccw_first_k)
        ccw_last = wrap(i_max + ccw_last_k)

        prev_f = n - 1 if ccw_first == 0 else ccw_first - 1
        next_l = 0 if ccw_last + 1 == n else ccw_last + 1

        # Boundary intersections with the cutting line.
        x = line_intersection(pts[prev_f], pts[ccw_first], a, d)
        y = line_intersection(pts[ccw_last], pts[next_l], a, d)

        # Shoelace contribution of polygon vertices ccw_first ... ccw_last.
        if ccw_first <= ccw_last:
            chain = pref[ccw_last] - pref[ccw_first]
        else:
            chain = pref[n] - pref[ccw_first] + pref[ccw_last]

        # Doubled area of the positive-side piece.
        doubled = (
            cross(x, pts[ccw_first])
            + chain
            + cross(pts[ccw_last], y)
            + cross(y, x)
        )

        piece = abs(doubled) / 2.0

        ans = min(piece, total_area - piece)

        # Clamp tiny negative floating point errors.
        if ans < 0:
            ans = 0.0

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

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


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

---

## 5. Compressed editorial

For a query line through `a` and `b`, let `d = b - a` and define:

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

This signed value tells which side of the line a point lies on.

Preprocess the convex polygon:

1. Make vertex order counterclockwise.
2. Compute prefix shoelace sums.
3. Find lexicographically leftmost and rightmost vertices.
4. These split the polygon into two convex chains.

On each chain, the values `side(vertex)` are unimodal for any fixed line. Therefore, binary search can find the maximum and minimum side value on each chain. Taking the best among both chains gives the polygon-wide maximum and minimum.

If the maximum is non-positive or the minimum is non-negative, the line does not split the polygon, so answer `0`.

Otherwise, let `i_min` and `i_max` be vertices with minimum and maximum side. Along the counterclockwise arc from `i_min` to `i_max`, side values go from negative to positive; along the other arc, they go from positive to negative. Binary search on these arcs finds the two crossed edges.

Compute the two intersection points with the cut line. The positive-side piece consists of:

```text
intersection1 → polygon vertices on positive side → intersection2
```

Use shoelace formula plus prefix sums to compute its area in `O(1)` after locating the edges.

The answer is:

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

Complexity:

```text
Preprocessing: O(N)
Each query:   O(log N)
Memory:       O(N)
```
