P16931 Astral Stele Needles

:::info[Background] As several "Gongchen Sealing Devices" collapsed with a loud crash, the ancient seal surrounding the "Sunken Star Library" finally showed a gap. The first thing that changed was the air. The magic that had been coiling around the area, so heavy that it was almost hard to breathe, slowly faded away like an ebbing tide. Right after that, the two long-sealed tall doors of the "Sunken Star Library" let out a deep and long rumble, as if some enormous creature that had slept for too long finally opened its eyes in the depths of time. The stone doors slowly opened to both sides. Fine dust fell from the cracks, drifting in the slanting light like a quiet and slow snowfall. "It's open..." Fern said softly. Behind the door was not the narrow corridor they had imagined, but an unusually wide forecourt. The ground was paved with large gray-white ancient stones, covered with extremely fine patterns, like some star chart worn down over countless years. Many black stone pillars of different heights were scattered across the forecourt. Some were already leaning or broken, while some still stood quietly, with dim crystal cores set into their tops. Looking closely, you could see very ancient spell-script carved beneath every pillar, and they were silently connected to each other by thin threads of magic that were almost impossible to see with the naked eye. "Are these also mechanisms?" Stark frowned. "Yes." Frieren nodded, her gaze slowly sweeping over the pillars scattered around. "These are called 'Astral Stele Needles'. Ancient mages used them as nodes for observation and defining boundaries. They do not look special by themselves, but once enough needles are activated, they will automatically connect into an outer edge and open a boundary barrier that covers the entire forecourt." Fern followed her line of sight. Sure enough, as the library doors opened, some needles that had been silent for a long time began to light up one after another. A faint blue glow slowly emerged from the tops of the pillars, like cold stars being awakened in the night. Between those lit nodes, thin beams of light kept linking and stretching, outlining unstable contours. "And this barrier is still changing." Frieren said softly. Some needles, worn by age, dimmed again shortly after lighting up. Others were reawakened by magic leaking from inside the library. Whenever a node changed, the faint light curtain above the forecourt would redraw its boundary accordingly, sometimes expanding outward and sometimes shrinking inward, like a transparent map whose shape was being constantly rewritten. "That means..." Stark looked at the flickering points of light, his expression gradually becoming complicated. "We have to keep figuring out how large the outermost ring is enclosing right now?" "Yes." Frieren's tone was still calm. "As long as we know how the outermost boundary is connected among all currently valid 'Astral Stele Needles', we can compute the area this barrier covers at this moment." She slightly raised her head and looked at the outline of light above the forecourt, which was still changing. :::

The ground of the library forecourt can be viewed as a Cartesian coordinate system. There are $n$ "Astral Stele Needles" on it, numbered $1\sim n$, where $n$ is even. The coordinates of the $i$-th "Astral Stele Needle" are $(x_i, y_i)$. It is guaranteed that all coordinates are pairwise distinct, and no three points are collinear. Frieren has already figured out the brightness changes of the "Astral Stele Needles". Specifically, for any angle $\theta\in[0,\pi)$, define the direction vector $u_\theta=(\cos\theta,\sin\theta)$. For each "Astral Stele Needle" $P_i=(x_i,y_i)$, define its projection value in this direction as $p_i(\theta)=x_i\cos\theta+y_i\sin\theta$. If at this angle **all $p_i(\theta)$ are pairwise distinct**, then this angle is called an "Astral Angle". For an "Astral Angle" $\theta$, sort all needle coordinates by the projection result $p_i(\theta)$ from small to large. Then the first $\frac{n}{2}$ "Astral Stele Needles" will light up. Let the convex hull area of these needles be $A_\theta$. Frieren needs to know twice the maximum convex hull area of the "Astral Stele Needles", that is, $$S=\max_{\theta\ \text{is an "Astral Angle"}} 2A_\theta $$ Since all coordinates are integers, it is guaranteed that the answer is an integer.

The first line contains an integer $n(2\leq n\leq 2\times 10^3)$, representing the number of "Astral Stele Needles". The $i$-th line contains two integers $x_i, y_i(-10^6\leq x_i, y_i\leq 10^6)$, representing the coordinates of the $i$-th "Astral Stele Needle".

Output one integer, representing twice the maximum convex hull area of the "Astral Stele Needles". $$S=\max_{\theta\ \text{is an "Astral Angle"}} 2A_\theta $$

Translated by ChatGPT 5