Submission details
Task:Broken car race
Sender:Makkara
Submission time:2025-11-08 15:25:51 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.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
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.01 sdetails
#20ACCEPTED0.01 sdetails
#21ACCEPTED0.07 sdetails
#22ACCEPTED0.08 sdetails
#23ACCEPTED0.10 sdetails
#24ACCEPTED0.11 sdetails
#250.04 sdetails
#260.04 sdetails
#270.06 sdetails
#280.06 sdetails

Compiler report

input/code.cpp: In lambda function:
input/code.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0; i<h.size(); i++) {
      |                  ~^~~~~~~~~

Code

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

struct Point {
  long long x, y;
  Point() {}
  Point(long long x, long long y) : x(x), y(y) {}
  bool operator < (const Point &p) const {
    return x < p.x || (x == p.x && y < p.y);
  }
};

bool cross(const Point &O, const Point &A, const Point &B) {
  return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector <Point> convex_hull(vector <Point> P) {
  int n = P.size(), k = 0;
  vector <Point> H(2*n);
  sort(P.begin(), P.end());
  for(int i=0; i<n; i++) {
    while(k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
    H[k++] = P[i];
  }
  for(int i=n-2, t = k+1; i>=0; i--) {
    while(k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
    H[k++] = P[i];
  }
  H.resize(k-1);
  return H;
}

int main() {
  int n;
  cin >> n;
  if(n < 4) {
    cout << "NO" << endl;
    return 0;
  }
  long long x, y;
  vector <Point> v;
  for(int i=0; i<n; i++) {
    cin >> x >> y;
    v.push_back(Point(x,y));
  }
  vector <Point> h = convex_hull(v);
  if(h.size() >= 4) {
    cout << "YES" << endl;
    for(int i=0; i<4; i++) {
      cout << h[i].x << " " << h[i].y << endl;
    }
    return 0;
  }
  if(n == 4) {
    cout << "NO" << endl;
    return 0;
  }
  auto isin = [&] (Point r) -> bool {
    for(int i=0; i<h.size(); i++) {
      if(h[i].x == r.x && h[i].y == r.y) return true;
    }
    return false;
  };
  vector <Point> tmp;
  for(int i=0; i<5 && tmp.size() < 2; i++) {
    if(isin(v[i])) continue;
    tmp.push_back(v[i]);
  }
  vector <Point> t1 = {h[0], h[1], tmp[0], tmp[1]};
  vector <Point> t2 = {h[0], h[2], tmp[0], tmp[1]};
  vector <Point> t3 = {h[2], h[1], tmp[0], tmp[1]};
  t1 = convex_hull(t1);
  t2 = convex_hull(t2);
  t3 = convex_hull(t3);
  if(t1.size() == 4) {
    cout << "YES" << endl;
    for(int i=0; i<4; i++) {
      cout << t1[i].x << " " << t1[i].y << endl;
    }
    return 0;
  }
  t1 = t2;
  if(t1.size() == 4) {
    cout << "YES" << endl;
    for(int i=0; i<4; i++) {
      cout << t1[i].x << " " << t1[i].y << endl;
    }
    return 0;
  }
  t1 = t3;
  if(t1.size() == 4) {
    cout << "YES" << endl;
    for(int i=0; i<4; i++) {
      cout << t1[i].x << " " << t1[i].y << endl;
    }
    return 0;
  }
  cout << "NO" << endl;
  return 0;
}

Test details

Test 1

Verdict:

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
0 1
1 0
1 1

Test 2

Verdict:

input
4
0 0
3 0
0 3
1 1

correct output
NO

user output
YES
0 0
0 3
1 1
3 0

Test 3

Verdict:

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

correct output
NO

user output
YES
-1000000000 -999999999
-999999999 -1000000000
999999999 999999999
1000000000 1000000000

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
YES
-1000000000 -1000000000
-1 -999999999
1 -999999999
1000000000 -999999998

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
YES
-999999999 -1000000000
0 -999999999
1 -999999999
1000000000 -999999998

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
YES
0 0
1 1
2 4
3 4

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
YES
0 0
1 1
2 4
3 4

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
YES
-947476077 -331979804
-947475987 -331979714
-947475897 -331979444
-947475807 -331979444

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
YES
-318972227 -438409225
-318972149 -438409147
-318972071 -438408913
-318971993 -438408913

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
YES
0 0
1 1
2 4
3 4

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
YES
0 0
1 1
2 4
3 4

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
YES
-298761158 -20751946
-298761080 -20751868
-298761002 -20751634
-298760924 -20751634

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
YES
-664720318 -463218529
-664720316 -463218527
-664720314 -463218521
-664720312 -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
1 1
2 4
3 9

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
1 1
2 4
3 9

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
-921893387 -773164998
-921893335 -773164842
-921893283 -773164582

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
-857989512 -260517350
-857989419 -260517071
-857989326 -260516606

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
1 1
2 4
3 9

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
1 1
2 4
3 9

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
-76010702 -505453310
-76010636 -505453112
-76010570 -505452782

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
-234627254 -986321047
-234627181 -986320828
-234627108 -986320463

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
1 1
2 4
317 486

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
1 1
2 4
317 486

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
-701962979 -481681059
-701962958 -481681038
-701962937 -481680975
-701956322 -481670853

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
-534305044 -499782441
-534304992 -499782389
-534304940 -499782233
-534288560 -499757169