CSES 2195 ↗

Convex Hull

All input points lying on the convex hull, in any order.

5
submissions
0.998
best score

Given a set of n points in the two-dimensional plane, your task is to determine the convex hull of the points.

Input

The first input line has an integer n: the number of points.

After this, there are n lines that describe the points. Each line has two integers x and y: the coordinates of a point.

You may assume that each point is distinct, and the area of the hull is positive.

Output

First print an integer k: the number of points in the convex hull.

After this, print k lines that describe the points. You can print the points in any order. Print all points that lie on the convex hull.

Constraints

  • 3≤n≤2⋅105
  • −109≤x,y≤109

Example

Input:

6
2 1
2 5
3 3
4 3
4 4
6 3

Output:

4
2 1
2 5
4 4
6 3

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/ConvexHull/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
2,136,846,9042,851,779,090

5 qualifying submissions. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

5 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj000.9982,136,846,904talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 20:53 UTC
2lukerj000.9752,275,724,470talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 02:18 UTC
3lukerj000.9502,711,251,187talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-21 22:04 UTC
4lukerj000.9482,503,781,182talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 01:16 UTC
5lukerj000.9362,851,779,090talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 22:14 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.