Broken car race

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

#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()

using ll = long long;

struct Angle {
	int x, y;
	int t;
	Angle(int x, int y, int t = 0) : x(x), y(y), t(t) {}
	Angle operator-(Angle b) const { return {x - b.x, y - b.y, t}; }
	int half() const {
		assert(x || y);
		return y < 0 || (y == 0 && x < 0);
	}
};

bool operator<(Angle a, Angle b) {
	return make_tuple(a.t, a.half(), a.y * (ll)b.x) <
		   make_tuple(b.t, b.half(), a.x * (ll)b.y);
}

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }

template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y) == tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x,y+p.y); }
	P operator-(P p) const { return P(x-p.x,y-p.y); }
	P operator*(T d) const { return P(x * d, y * d); }
	P operator/(T d) const { return P(x / d, y / d); }
	T dot(P p) const { return x * p.x + y * p.y; }
	T cross(P p) const { return x * p.y - y * p.x; }
	T cross(P a, P b) const { return (a - *this).cross(b - *this); }
};

typedef Point<ll> P;

vector<P> convexHull(vector<P> pts) {
	if (sz(pts) <= 1) return pts;
	sort(all(pts));
	vector<P> h(sz(pts) + 1);
	int s = 0, t = 0;
	for (int it = 2; it--; s = --t, reverse(all(pts)))
		for (P p : pts) {
			while (t >= s + 2 && h[t - 2].cross(h[t - 1], p) <= 0) t--;
			h[t++] = p;
		}
	return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<P> p(n);
	for (int i = 0; i < n; ++i) {
		cin >> p[i].x >> p[i].y;
	}

	auto c = convexHull(p);

	if (sz(c) >= 4) {
		cout << "YES" << endl;
		for (int i = 0; i < 4; ++i) {
			cout << c[i].x << " " << c[i].y << endl;
		}
		return 0;
	}


	if (sz(c) < 3) {
		cout << "NO" << endl;
		return 0;
	}


	vector<P> opt;

	for (int i = 0; i < n; ++i) {
		bool f = 0;
		for (auto u : c) if (p[i] == u) f = 1;
		for (auto u : opt) if (p[i] == u) f = 1;
		if (!f) {
			opt.push_back(p[i]);
		}
		if (sz(opt) >= 2) break;
	}

	if (sz(opt) < 2) {
		cout << "NO" << endl;
		return 0;
	}

	auto test = [&](vector<P> t) {
		auto ct = convexHull(t);
		if (sz(ct) == 4) {
			cout << "YES" << endl;
			for (int i = 0; i < 4; ++i) {
				cout << ct[i].x << " " << ct[i].y << endl;
			}
			exit(0);
		}
	};

	for (int i = 0; i < 3; ++i) {
		test({c[i], c[(i + 1) % 3], opt[0], opt[1]});
	}

	assert(false);
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED