Submission details
Task:Broken car race
Sender:All dO(n³)
Submission time:2025-11-08 14:58:08 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#90.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#160.00 sdetails
#170.01 sdetails
#180.01 sdetails
#190.01 sdetails
#200.01 sdetails
#21ACCEPTED0.12 sdetails
#22ACCEPTED0.12 sdetails
#230.15 sdetails
#240.16 sdetails
#250.06 sdetails
#260.06 sdetails
#270.08 sdetails
#280.08 sdetails

Compiler report

input/code.cpp: In function 'std::vector<std::complex<double> > convex_hull(std::vector<std::complex<double> >&)':
input/code.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (auto i = 0; i < points.size(); i++) {
      |                      ~~^~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < dnhull.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
input/code.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i = 1; i < uphull.size() - 1; i++) {...

Code

#include <bits/stdc++.h>
#include <complex.h>
using namespace std;

#define all(arr) begin(arr), end(arr)

typedef complex<double> P;

const long long mod = pow(10, 9) + 7;

#define PI 3.141

long long fact(long long i) {
    long long n = i;
    while(i--) n *= i;
    return n;
}

int nxt() {
    int n;
    cin >> n;
    return n;
}

bool comp(P a, P b) {
    if (a.real() < b.real()) {
        return true;
    }else if (a.real() == b.real()) {
        return a.imag() < b.imag();
    }
    return false;
}

double angle(P a, P b) {
    return arg(b) - arg(a);
}

vector<P> convex_hull(vector<P>& points) {
    vector<P> hull;
    for (auto i = 0; i < points.size(); i++) {
        hull.push_back(points[i]);
        if (hull.size() > 2) {
            auto v0 = hull.end() - 3;
            auto v1 = hull.end() - 2;
            auto v2 = hull.end() - 1;

            auto a = *v2 - *v1;
            auto b = *v0 - *v1;
            auto c = angle(a, b);
            if (c < 0 || c > numbers::pi) {
                hull.erase(v1);
            }
        }
    }
    return hull;
}

int main () {
    //freopen("input.txt", "r", stdin);

    int n = nxt();
    vector<P> points;

    for (int i = 0; i< n; i++) {
        double x, y;
        cin >> x >> y;
        points.push_back({x, y});
    }

    sort(all(points), comp);
    auto dnhull = convex_hull(points);

    if (dnhull.size() >= 4) {
        for (int i = 0; i < 4; i++) {
            auto pt = dnhull[i];
            cout << pt.real() << " " << pt.imag() << "\n";
        }
        return 0;
    }

    sort(points.rbegin(), points.rend(), comp);
    auto uphull = convex_hull(points);

    if (dnhull.size() + uphull.size() - 2 >= 4) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
        return 0;
    }

    int count = 0;
    for (int i = 0; i < dnhull.size(); i++) {
        auto pt = dnhull[i];
        cout << pt.real() << " " << pt.imag() << "\n";
        count++;
    }

    if (uphull.size() > 1) {
        for (int i = 1; i < uphull.size() - 1; i++) {
            if (count == 4) {
                return 0;
            }
            auto pt = uphull[i];
            cout << pt.real() << " " << pt.imag() << "\n";
            count++;
        }
    }

    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:

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

correct output
NO

user output
YES
-1e+09 -1e+09
-1e+09 -1e+09
1e+09 1e+09
1e+09 1e+09

Test 4

Verdict:

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

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

user output
NO

Test 5

Verdict:

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

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

user output
NO

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:

input
4
0 0
1 1
2 4
3 4

correct output
YES
0 0
1 1
3 4
2 4

user output
NO

Test 10

Verdict:

input
4
3 4
0 0
1 1
2 4

correct output
YES
0 0
1 1
3 4
2 4

user output
NO

Test 11

Verdict:

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

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

user output
NO

Test 12

Verdict:

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

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

user output
NO

Test 13

Verdict:

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

correct output
YES
0 0
1 1
3 4
2 4

user output
NO

Test 14

Verdict:

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

correct output
YES
0 0
1 1
3 4
2 4

user output
NO

Test 15

Verdict:

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

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

user output
NO

Test 16

Verdict:

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

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

user output
NO

Test 17

Verdict:

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
999 100
978 961
965 927

Test 18

Verdict:

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
999 100
978 961
965 927

Test 19

Verdict:

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

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

user output
YES
-9.21893e+08 -7.73165e+08
-9.21841e+08 -7.7316e+08
-9.21843e+08 -7.73115e+08
-9.21843e+08 -7.73117e+08

Test 20

Verdict:

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

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

user output
YES
-8.5799e+08 -2.60517e+08
-8.57897e+08 -2.60508e+08
-8.57899e+08 -2.60428e+08
-8.579e+08 -2.60431e+08

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
99999 16
99687 99856
99556 99806

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
99999 16
99687 99856
99556 99806

Test 23

Verdict:

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

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

user output
YES
-7.60108e+07 -5.05453e+08
-6.94108e+07 -5.05452e+08
-6.94314e+07 -4.98863e+08
-6.94401e+07 -4.98866e+08

Test 24

Verdict:

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

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

user output
YES
-2.34627e+08 -9.86321e+08
-2.27327e+08 -9.8632e+08
-2.2735e+08 -9.79032e+08
-2.2736e+08 -9.79035e+08

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
YES
0 0
99999 16
99555 698
99295 1249

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
YES
0 0
99999 16
99555 698
99295 1249

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
YES
-7.01963e+08 -4.81681e+08
-6.99863e+08 -4.81681e+08
-6.99872e+08 -4.81666e+08
-6.99878e+08 -4.81655e+08

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
YES
-5.34305e+08 -4.99782e+08
-5.29105e+08 -4.99782e+08
-5.29128e+08 -4.99746e+08
-5.29142e+08 -4.99717e+08