Cod sursa(job #2699455)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 24 ianuarie 2021 15:58:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>
#include <assert.h>
#include <iostream>

using namespace std;
using ll = long long;

#define fast_cin() 	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

//VARIABLES

struct POINT {
	double x, y;
} point[120005];

vector <POINT> up, down;

//FUNCTIONS

bool cmp(POINT a, POINT b) {
	if (a.x == b.x) {
		return a.y < b.y;
	}
	return a.x < b.x;
}

double det(POINT a, POINT b, POINT c) {
	return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.y * b.x - a.x * c.y;
}

//MAIN
int main() {

	#ifdef INFOARENA
		freopen("infasuratoare.in", "r", stdin);
		freopen("infasuratoare.out", "w", stdout);
	#endif

	fast_cin();
	
	int n; cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> point[i].x >> point[i].y;
	}

	sort(point + 1, point + n + 1, cmp);

	for (int i = 1; i <= n; i++) {
		while (down.size() > 1 && det(down[down.size() - 2], down[down.size() - 1], point[i]) <= 0) {
			down.pop_back();
		}
		down.push_back(point[i]);			   
	}

	for (int i = n; i >= 1; i--) {
		while (up.size() > 1 && det(up[up.size() - 2], up[up.size() - 1], point[i]) <= 0) {
			up.pop_back();
		}
		up.push_back(point[i]);
	}

	cout << down.size() + up.size() - 2 << '\n';

	for (int i = 0; i < down.size() - 1; i++) {
		cout << setprecision(12) << fixed << down[i].x << ' ' << down[i].y << '\n';
	}

	for (int i = 0; i < up.size() - 1; i++) {
		cout << setprecision(12) << fixed << up[i].x << ' ' << up[i].y << '\n';
	}

	return 0;
}