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

277. Heroes
Time limit per test: 1 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



In the game 'Heroes of keyboard and mouse' there are some cities at the plane; each city is situated in a point. The player can build some new cities. All the cities are surrounded by a polygonal wall of minimal length. When a city is built, the wall may be rebuilt to include it. Your task is to determine the area inside the wall each time a new city is built. Of course, the cities are in distinct points.

Input
The game starts with three cities with coordinates (x1,y1), (x2,y2) and (x3,y3), which are given in the first line of the input. The initial area inside the wall is non-negative. The second line of the input contains single integer N (1≤ N≤ 100000), being the number of cities to be built. Each of the next N lines contains the coordinates of a city to be built. All the coordinates are integer and do not exceed 108 by absolute value.

Output
The K-th line of the output (1≤ K≤ N) must contain an integer, being the doubled area inside the wall after building K first cities (as listed in the input, not including the first three).

Example(s)
sample input
sample output
1 0 0 3 3 2
5
1 2
2 1
3 0
2 3
0 1
8
8
12
14
16



Novosibirsk SU Contest #2, by Novosibirsk Team #1

<|response|>
## 1) Abridged problem statement (concise)

You are given 3 initial distinct points on a plane. Then **N** more distinct points are added one by one (in given order).  
After each insertion, all points are surrounded by a polygonal wall of **minimum length** (perimeter). That wall is the **convex hull** of the points.

For each of the N insertions, output the **doubled area** of the current convex hull (an integer).

Constraints: `N ≤ 100000`, coordinates are integers with `|x|, |y| ≤ 1e8`.

---

## 2) Key observations

1. **Minimum-perimeter enclosing polygon = convex hull.**  
   So after each new point we need the area of the convex hull of all points seen so far.

2. **Doubled area of a polygon** with vertices in order is:
   \[
   2S = \left|\sum_{i=0}^{m-1} (P_i \times P_{i+1})\right|
   \]
   where \(P_i \times P_{i+1} = x_i y_{i+1} - y_i x_{i+1}\) and indices wrap around.

3. Recomputing the convex hull from scratch after each insertion is too slow.  
   We need a **dynamic / incremental convex hull** with ~`O(log n)` amortized update.

4. Represent the convex hull as two **x-monotone chains**:
   - **lower hull** (leftmost → rightmost along the bottom)
   - **upper hull** (leftmost → rightmost along the top)

   Each chain can be maintained in an ordered structure by `(x, y)` and repaired locally (like Graham scan).

5. If we maintain, for each chain, the sum of cross products of consecutive points, then we can get the hull’s doubled area quickly by combining those sums (plus endpoint “connections” if endpoints differ).

---

## 3) Full solution approach

### Data structure
Maintain:
- `lower`: ordered set of points on the lower chain (sorted by `(x, y)`).
- `upper`: ordered set of points on the upper chain.
- `lower_sum`: \(\sum (L_i \times L_{i+1})\) over consecutive points in `lower`.
- `upper_sum`: \(\sum (U_i \times U_{i+1})\) over consecutive points in `upper`.

### Insertion into one chain (core idea)
To insert point `p` into a chain (lower or upper), do:

1. **Find neighbors by x** using `lower_bound(p)`:
   - `right` = first point in chain with key ≥ `p`
   - `left` = previous point (if exists)

2. **Same x special case**  
   For a fixed `x`, only one point can belong to a monotone hull chain:
   - lower chain keeps the **minimum y**
   - upper chain keeps the **maximum y**

   If `p` is not more extreme than the existing point with same `x`, ignore it.  
   Otherwise replace that point, updating the cross-sum around it.

3. **Check if `p` is useless locally**  
   If both neighbors exist and `p` lies “inside” that chain (does not make it more convex outward), ignore it.

4. **Remove points that become internal** (like Graham scan):
   - While the turn with `p` violates convexity on the left side, delete the left neighbor.
   - Similarly delete violating points on the right side.
   Each deleted point is removed once overall ⇒ amortized linear deletions.

5. **Insert `p` and update cross-sum**  
   Remove old edge `(left,right)` if it existed, then add new edges `(left,p)` and `(p,right)`.

We run this procedure twice per point:
- for **lower** with one convexity direction
- for **upper** with the opposite direction

This is implemented via a `sign` parameter (`+1` lower, `-1` upper) that flips orientation tests.

### Computing doubled area from the two chains
The convex hull boundary is:
- lower chain from left→right
- then upper chain from right→left

We maintain:
- `lower_sum` = sum along lower chain left→right
- `upper_sum` = sum along upper chain left→right

Then:
- traversing upper in reverse negates its cross-sum contribution, so a working formula is:
  \[
  \text{doubled\_area\_signed} = \text{lower\_sum} - \text{upper\_sum} + \text{endpoint corrections}
  \]
Endpoint corrections are needed when the leftmost/rightmost points differ between chains due to degeneracies.

Finally output `abs(doubled_area_signed)`.

### Complexity
- Each insertion does `O(log n)` set operations + amortized `O(1)` deletions.
- Total: **amortized `O(N log N)`**, fits easily for `N=100000`.

---

## 4) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>
// #include <coding_library/geometry/dynamic_convex_hull.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 = int64_t;

struct Point {
    static constexpr coord_t eps = 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
        );
    }
};

class DynamicConvexHull {
  public:
    set<Point> lower;
    set<Point> upper;

  private:
    coord_t lower_sum = 0;
    coord_t upper_sum = 0;

    using Iter = set<Point>::iterator;

    void add_to_hull(set<Point>& hull, coord_t& sum, const Point& p, int sign) {
        if(hull.empty()) {
            hull.insert(p);
            return;
        }

        auto right = hull.lower_bound(p);

        if(right != hull.end() && right->x == p.x) {
            if(sign * (p.y - right->y) >= 0) {
                return;
            }
            Iter left = (right != hull.begin()) ? prev(right) : hull.end();
            Iter right_next = next(right);
            if(left != hull.end()) {
                sum -= (*left) ^ (*right);
            }
            if(right_next != hull.end()) {
                sum -= (*right) ^ (*right_next);
            }
            if(left != hull.end() && right_next != hull.end()) {
                sum += (*left) ^ (*right_next);
            }
            hull.erase(right);
            right = right_next;
        }

        Iter left = (right != hull.begin()) ? prev(right) : hull.end();

        if(left != hull.end() && right != hull.end()) {
            if(sign * ccw(*left, *right, p) >= 0) {
                return;
            }
            sum -= (*left) ^ (*right);
        }

        while(left != hull.end() && left != hull.begin()) {
            Iter left_left = prev(left);
            if(sign * ccw(*left_left, *left, p) > 0) {
                break;
            }
            sum -= (*left_left) ^ (*left);
            hull.erase(left);
            left = left_left;
        }

        while(right != hull.end()) {
            Iter right_next = next(right);
            if(right_next == hull.end()) {
                break;
            }
            if(sign * ccw(p, *right, *right_next) > 0) {
                break;
            }
            sum -= (*right) ^ (*right_next);
            hull.erase(right);
            right = right_next;
        }

        if(left != hull.end()) {
            sum += (*left) ^ p;
        }
        if(right != hull.end()) {
            sum += p ^ (*right);
        }

        hull.insert(p);
    }

  public:
    DynamicConvexHull() = default;

    void add(const Point& p) {
        add_to_hull(lower, lower_sum, p, 1);
        add_to_hull(upper, upper_sum, p, -1);
    }

    coord_t doubled_area() const {
        if(lower.empty() || upper.empty()) {
            return 0;
        }

        coord_t result = lower_sum - upper_sum;

        const Point& right_lower = *lower.rbegin();
        const Point& right_upper = *upper.rbegin();
        if(!(right_lower == right_upper)) {
            result += right_lower ^ right_upper;
        }

        const Point& left_lower = *lower.begin();
        const Point& left_upper = *upper.begin();
        if(!(left_lower == left_upper)) {
            result += left_upper ^ left_lower;
        }

        return result;
    }
};

Point a, b, c;
int q;

void read() {
    cin >> a >> b >> c;
    cin >> q;
}

DynamicConvexHull hull;

void solve() {
    // The idea is to do a dynamic convex hull after every operation. In
    // particular, we will maintain the lower and upper envelope and we will
    // maintain the area separately. The envelope will be maintained as a set of
    // points, sorted by X. We will then add points one by one, and binary
    // search in the set to find it's desired place. There are then two cases -
    // the point we are adding is inside of the polygon in which case we can
    // skip it, or outside meaning we need to potentially remove some of the
    // points already in the hull. Removing points can be done similarly to
    // Graham scan's algorithm and the complexity will be amortized O(log)
    // (because of the set).
    // To find the area, we can remember that the area of the polygon can be
    // given by the absolute of the sum of the determinants of the 2x2 matrices
    // given by each two consecutive points.

    hull.add(a);
    hull.add(b);
    hull.add(c);

    for(int i = 0; i < q; i++) {
        Point p;
        cin >> p;
        hull.add(p);
        cout << abs(hull.doubled_area()) << '\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;
}
```

---

## 5) Python implementation (detailed comments)

Python has no built-in balanced BST like `std::set`. To keep the same algorithmic guarantees you’d typically need an external library (e.g. `sortedcontainers`), which is usually not allowed.

Below is a **correct educational reference** using a sorted list + `bisect`. It is **O(N)** per insertion in the worst case due to list insert/delete, and may TLE for `N=100000` in strict limits. The C++ version is the intended performant solution.

```python
import sys
from bisect import bisect_left

def cross(a, b):
    """2D cross product of points/vectors a and b (tuples (x,y))."""
    return a[0] * b[1] - a[1] * b[0]

def ccw(a, b, c):
    """Orientation of triangle (a,b,c): +1 CCW, -1 CW, 0 collinear."""
    v = cross((b[0]-a[0], b[1]-a[1]), (c[0]-a[0], c[1]-a[1]))
    if v == 0:
        return 0
    return 1 if v > 0 else -1

class DynamicConvexHull:
    """
    Reference implementation of the same idea as the C++ solution:
    maintain lower and upper x-monotone chains, and keep cross-sums.
    Uses Python lists => insert/delete is O(n).
    """

    def __init__(self):
        self.lower = []
        self.upper = []
        self.lower_sum = 0
        self.upper_sum = 0

    def _erase_at(self, hull, i, s):
        """
        Remove hull[i] and update cross-sum s that represents
        Σ cross(hull[j], hull[j+1]) for consecutive points.
        """
        p = hull[i]
        has_left = i - 1 >= 0
        has_right = i + 1 < len(hull)

        if has_left:
            s -= cross(hull[i-1], p)
        if has_right:
            s -= cross(p, hull[i+1])
        if has_left and has_right:
            s += cross(hull[i-1], hull[i+1])

        hull.pop(i)
        return s

    def _add_to_chain(self, hull, s, p, sign):
        """Insert point p into one chain. sign=+1 lower, sign=-1 upper."""
        if not hull:
            hull.append(p)
            return s

        i = bisect_left(hull, p)

        # same-x handling
        if i < len(hull) and hull[i][0] == p[0]:
            existing = hull[i]
            # lower wants min y, upper wants max y
            if sign * (p[1] - existing[1]) >= 0:
                return s
            s = self._erase_at(hull, i, s)  # remove existing

        # neighbors
        left = hull[i-1] if i-1 >= 0 else None
        right = hull[i] if i < len(hull) else None

        # local inside test
        if left is not None and right is not None:
            if sign * ccw(left, right, p) >= 0:
                return s
            s -= cross(left, right)  # break (left,right)

        # fix left side
        while i-1 >= 1:
            a = hull[i-2]
            b = hull[i-1]
            if sign * ccw(a, b, p) > 0:
                break
            s = self._erase_at(hull, i-1, s)
            i -= 1  # insertion index shifts left

        # fix right side
        while i < len(hull) - 1:
            b = hull[i]
            c = hull[i+1]
            if sign * ccw(p, b, c) > 0:
                break
            s = self._erase_at(hull, i, s)
            # i stays the same (elements shift left)

        # reconnect
        left = hull[i-1] if i-1 >= 0 else None
        right = hull[i] if i < len(hull) else None
        if left is not None:
            s += cross(left, p)
        if right is not None:
            s += cross(p, right)

        hull.insert(i, p)
        return s

    def add(self, p):
        self.lower_sum = self._add_to_chain(self.lower, self.lower_sum, p, +1)
        self.upper_sum = self._add_to_chain(self.upper, self.upper_sum, p, -1)

    def doubled_area_signed(self):
        if not self.lower or not self.upper:
            return 0

        res = self.lower_sum - self.upper_sum

        rl, ru = self.lower[-1], self.upper[-1]
        if rl != ru:
            res += cross(rl, ru)

        ll, lu = self.lower[0], self.upper[0]
        if ll != lu:
            res += cross(lu, ll)

        return res

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    a = (int(next(it)), int(next(it)))
    b = (int(next(it)), int(next(it)))
    c = (int(next(it)), int(next(it)))
    n = int(next(it))

    hull = DynamicConvexHull()
    hull.add(a); hull.add(b); hull.add(c)

    out = []
    for _ in range(n):
        p = (int(next(it)), int(next(it)))
        hull.add(p)
        out.append(str(abs(hull.doubled_area_signed())))

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

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

If you want a Python solution that is also fast under these constraints, tell me which platforms/libraries are allowed (e.g., PyPy, `sortedcontainers`, or implementing a custom treap), and I’ll provide an `O(N log N)` Python version.