Broken car race

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

#define rep(i, a, b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int sgn(int x) {
    if (x == 0) return 0;
    if (x < 0) return -1;
    return 1;
}

struct Point{
    int x, y;
    Point(int xx, int yy) {
        x =xx;
        y=yy;
    }
    bool operator<(Point b) const {
        if(x==b.x)return y<b.y;
        return x<b.x;
    }
    Point operator-(const Point& b) const {
        return Point(x-b.x, y-b.y);
    }
    int operator^(const Point& b) const {
        return x*b.y-y*b.x;
    }
    int distance(Point p){
        return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);
    }
};

struct cmp{
    Point p = Point(0, 0);
    cmp(const Point &p0){
        p = Point(p0.x, p0.y);
    }
    bool operator () (const Point&aa, const Point& bb) {
        Point a=aa, b=bb;
        int d = sgn((a-p)^(b-p));
        if (d==0) {
            return sgn(a.distance(p)-b.distance(p)) < 0;
        }
        return d>0;
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n;
    cin >> n;

    vector<Point> a(n, Point(0, 0));
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = Point(x, y);
    }

    Point mi = a[0];
    for (int i=1; i <n; i++) {
        mi = min(mi, a[i]);
    }
    sort(a.begin(), a.end(), cmp(mi));

    for (int i = 1; i + 2 < n; i++) {
        cerr << i << '\n';
        // 0, i, i + 1, i + 2
        vector<Point> pts = {a[0], a[i], a[i + 1], a[i + 2]};

        bool s[3];
        s[0] = false;
        s[1] = false;
        s[2] = false;
        bool good = true;
        for (int ii = 0; ii < 4; ii++) {
            int jj = (ii + 1) % 4;
            int kk = (jj + 1) % 4;
            s[sgn((pts[jj]-pts[ii])^(pts[kk]-pts[ii]))+1]=true;
            // cerr << pts[ii].x << ' ' << pts[ii].y << '|';
            // cerr << pts[jj].x << ' ' << pts[jj].y << '|';
            // cerr << pts[kk].x << ' ' << pts[kk].y << '|';
            // cerr << ' ' << s[0] << ' ' << s[2] << '\n';
            
            if(s[0]&&s[2]) {
                good = false;
                break;
            }
        }

        if (good) {
            cout << "YES\n";
            for (int j = 0; j < 4; j++) {
                cout << pts[j].x << ' ' << pts[j].y << '\n';
            }
            return 0;
        }
    }

    cout << "NO\n";
}

Test 1

Verdict: ACCEPTED

1

Test 2

Verdict: ACCEPTED

1

Test 3

Verdict: ACCEPTED

1

Test 4

Verdict: ACCEPTED

1

Test 5

Verdict: ACCEPTED

1

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

1

Test 10

Verdict: ACCEPTED

1

Test 11

Verdict: ACCEPTED

1

Test 12

Verdict: ACCEPTED

1

Test 13

Verdict: ACCEPTED

1
2

Test 14

Verdict: ACCEPTED

1
2

Test 15

Verdict: ACCEPTED

1
2

Test 16

Verdict: ACCEPTED

1
2

Test 17

Verdict: ACCEPTED

1
2
3

Test 18

Verdict: ACCEPTED

1
2
3

Test 19

Verdict: ACCEPTED

1
2
3

Test 20

Verdict: ACCEPTED

1
2
3

Test 21

Verdict: ACCEPTED

1
2

Test 22

Verdict: ACCEPTED

1
2

Test 23

Verdict: ACCEPTED

1
2

Test 24

Verdict: ACCEPTED

1
2

Test 25

Verdict: ACCEPTED

1

Test 26

Verdict: ACCEPTED

1

Test 27

Verdict: ACCEPTED

1

Test 28

Verdict: ACCEPTED

1