Submission details
Task:Broken car race
Sender:solosolve
Submission time:2025-11-08 15:35:50 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.04 sdetails
#22ACCEPTED0.04 sdetails
#23ACCEPTED0.04 sdetails
#24ACCEPTED0.05 sdetails
#250.02 sdetails
#260.02 sdetails
#270.02 sdetails
#280.03 sdetails

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct Vector
{
    ll x, y;

    Vector():
        x(0),
        y(0)
    {
    }

    Vector(Vector start, Vector finish):
        x(finish.x - start.x),
        y(finish.y - start.y)
    {
    }
};

ll cross(Vector a, Vector b)
{
    return a.x * b.y - a.y * b.x;
}

int main()
{
    ios_base::sync_with_stdio(false);

    ll n;
    cin >> n;

    vector<Vector> points(n);
    for (auto &it : points)
        cin >> it.x >> it.y;

    for (ll i = 1; i < n; i++)
        if (points[i].x < points[0].x || points[i].y < points[0].y)
            swap(points[0], points[i]);

    auto start = points[0];
    sort(points.begin() + 1, points.end(), [start](auto lhs, auto rhs) {
        return cross(Vector(start, lhs), Vector(start, rhs)) > 0;
    });

    vector<Vector> hull;
    hull.push_back(points[0]);

    for (ll i = 1; i < (ll)points.size(); i++)
    {
        while ((hull.size() >= 2) && (cross(Vector(hull[hull.size() - 2], hull[hull.size() - 1]), Vector(hull[hull.size() - 1], points[i])) < 0))
            hull.pop_back();
        hull.push_back(points[i]);
    }

    if (hull.size() < 4)
    {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";

    for (int i = 0; i < 4; i++)
        cout << hull[i].x << ' ' << hull[i].y << '\n';

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
4
0 0
1 1
0 1
1 0

correct output
YES
0 0
1 0
1 1
0 1

user output
YES
0 0
1 0
1 1
0 1

Test 2

Verdict: ACCEPTED

input
4
0 0
3 0
0 3
1 1

correct output
NO

user output
NO

Test 3

Verdict: ACCEPTED

input
4
-999999999 -1000000000
-1000000000 -999999999
1000000000 1000000000
999999999 999999999

correct output
NO

user output
NO

Test 4

Verdict: ACCEPTED

input
4
-1 -999999999
-1000000000 -1000000000
1 -999999999
1000000000 -999999998

correct output
YES
-1000000000 -1000000000
1 -999999999
1000000000 -999999998
-1 -999999999

user output
YES
-1000000000 -1000000000
1 -999999999
1000000000 -999999998
-1 -999999999

Test 5

Verdict: ACCEPTED

input
4
0 -999999999
-999999999 -1000000000
1 -999999999
1000000000 -999999998

correct output
YES
-999999999 -1000000000
1 -999999999
1000000000 -999999998
0 -999999999

user output
YES
-999999999 -1000000000
1 -999999999
1000000000 -999999998
0 -999999999

Test 6

Verdict: ACCEPTED

input
1
0 0

correct output
NO

user output
NO

Test 7

Verdict: ACCEPTED

input
2
0 0
1 1

correct output
NO

user output
NO

Test 8

Verdict: ACCEPTED

input
3
0 0
1 1
2 1

correct output
NO

user output
NO

Test 9

Verdict: ACCEPTED

input
4
0 0
1 1
2 4
3 4

correct output
YES
0 0
1 1
3 4
2 4

user output
YES
0 0
1 1
3 4
2 4

Test 10

Verdict: ACCEPTED

input
4
3 4
0 0
1 1
2 4

correct output
YES
0 0
1 1
3 4
2 4

user output
YES
0 0
1 1
3 4
2 4

Test 11

Verdict: ACCEPTED

input
4
-947476077 -331979804
-947475987 -331979714
-947475897 -331979444
-947475807 -331979444

correct output
YES
-947476077 -331979804
-947475987 -331979714
-947475807 -331979444
-947475897 -331979444

user output
YES
-947476077 -331979804
-947475987 -331979714
-947475807 -331979444
-947475897 -331979444

Test 12

Verdict: ACCEPTED

input
4
-318972071 -438408913
-318972227 -438409225
-318971993 -438408913
-318972149 -438409147

correct output
YES
-318972227 -438409225
-318972149 -438409147
-318971993 -438408913
-318972071 -438408913

user output
YES
-318972227 -438409225
-318972149 -438409147
-318971993 -438408913
-318972071 -438408913

Test 13

Verdict: ACCEPTED

input
5
0 0
1 1
2 4
3 4
...

correct output
YES
0 0
1 1
3 4
2 4

user output
YES
0 0
4 1
3 4
2 4

Test 14

Verdict: ACCEPTED

input
5
2 4
3 4
4 1
0 0
...

correct output
YES
0 0
1 1
3 4
2 4

user output
YES
0 0
4 1
3 4
2 4

Test 15

Verdict: ACCEPTED

input
5
-298761158 -20751946
-298761080 -20751868
-298761002 -20751634
-298760924 -20751634
...

correct output
YES
-298761158 -20751946
-298761080 -20751868
-298760924 -20751634
-298761002 -20751634

user output
YES
-298761158 -20751946
-298760846 -20751868
-298760924 -20751634
-298761002 -20751634

Test 16

Verdict: ACCEPTED

input
5
-664720312 -463218521
-664720310 -463218527
-664720318 -463218529
-664720316 -463218527
...

correct output
YES
-664720318 -463218529
-664720316 -463218527
-664720312 -463218521
-664720314 -463218521

user output
YES
-664720318 -463218529
-664720310 -463218527
-664720312 -463218521
-664720314 -463218521

Test 17

Verdict: ACCEPTED

input
1000
0 0
1 1
2 4
3 9
...

correct output
YES
0 0
1 1
2 4
3 9

user output
YES
0 0
860 3
964 7
977 15

Test 18

Verdict: ACCEPTED

input
1000
258 979
961 286
526 210
359 738
...

correct output
YES
258 979
359 738
961 286
938 1005

user output
YES
0 0
860 3
964 7
977 15

Test 19

Verdict: ACCEPTED

input
1000
-921893439 -773165050
-921893387 -773164998
-921893335 -773164842
-921893283 -773164582
...

correct output
YES
-921893439 -773165050
-921893387 -773164998
-921893335 -773164842
-921893283 -773164582

user output
YES
-921893439 -773165050
-921848719 -773164894
-921843311 -773164686
-921842635 -773164270

Test 20

Verdict: ACCEPTED

input
1000
-857937339 -260514932
-857900604 -260453645
-857927295 -260433371
-857907672 -260495123
...

correct output
YES
-857970726 -260438486
-857937339 -260514932
-857907672 -260495123
-857927295 -260433371

user output
YES
-857989605 -260517443
-857909625 -260517164
-857899953 -260516792
-857898744 -260516048

Test 21

Verdict: ACCEPTED

input
100000
0 0
1 1
2 4
3 9
...

correct output
YES
0 0
1 1
2 4
3 9

user output
YES
0 0
55522 6
91418 14
99999 16

Test 22

Verdict: ACCEPTED

input
100000
48266 36871
12387 33167
41280 87283
87910 36263
...

correct output
YES
41172 82734
48266 36871
87910 36263
41280 87283

user output
YES
0 0
55522 6
91418 14
99999 16

Test 23

Verdict: ACCEPTED

input
100000
-76010768 -505453376
-76010702 -505453310
-76010636 -505453112
-76010570 -505452782
...

correct output
YES
-76010768 -505453376
-76010702 -505453310
-76010636 -505453112
-76010570 -505452782

user output
YES
-76010768 -505453376
-72346316 -505452980
-69977180 -505452452
-69410834 -505452320

Test 24

Verdict: ACCEPTED

input
100000
-229347383 -980287597
-234601047 -984160539
-228269246 -981952727
-228868065 -980735452
...

correct output
YES
-234601047 -984160539
-229520466 -983763565
-228868065 -980735452
-229347383 -980287597

user output
YES
-234627327 -986321120
-230574221 -986320682
-227953813 -986320098
-227327400 -986319952

Test 25

Verdict:

input
49935
0 0
1 1
2 4
317 486
...

correct output
YES
0 0
1 1
317 486
2 4

user output
NO

Test 26

Verdict:

input
49935
32628 54449
63501 56035
40017 12250
62461 59485
...

correct output
YES
32628 54449
40017 12250
59069 42091
62461 59485

user output
NO

Test 27

Verdict:

input
49935
-701962979 -481681059
-701962958 -481681038
-701962937 -481680975
-701956322 -481670853
...

correct output
YES
-701962979 -481681059
-701962958 -481681038
-701956322 -481670853
-701962937 -481680975

user output
NO

Test 28

Verdict:

input
49935
-534092520 -499622905
-532312144 -496581113
-529779120 -499152565
-532498252 -497270841
...

correct output
YES
-534092520 -499622905
-532498252 -497270841
-532169300 -496736281
-532312144 -496581113

user output
NO