Cod sursa(job #2787520)

Utilizator bubblegumixUdrea Robert bubblegumix Data 23 octombrie 2021 17:03:22
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<map>
#include<numeric>
#include<unordered_set>
#include<iomanip>
#include<unordered_map>
#include<vector>
#include<stack>
#include<queue>
#include<limits>
#define all(v) v.begin(),v.end()
#define sorti(v) sort(all(v))
#define desc(x) greater<x>()
#define lsb(x) ((x)&(-x))
#define sortd(v) sort(all(v),desc(decltype(v[0])))
#define hmap unordered_map 
#define var auto&
#define hset unordered_set
#define pq priority_queue
#define inf 0x3f3f3f3f
#define exists(x,v) (v.find(x)!=v.end())
#define inrange(x,a,b) (x>=a && x<=b)
#define printv(v) {for(auto it:v) cout<<it<<' ';cout<<'\n';}
#define printa(v,a,b) {for(int i=a;i<=b;i++ ) cout<<v[i]<<' ';cout<<'\n';}
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef pair<double, double> pdd;
typedef vector<pdd> vdd;
template<typename T> T gcd(T a, T b) { T c; while (b) { c = a % b; a = b; b = c; }return a; }
template<typename T> T exp(T a, T n, T m) { T p = 1; while (n) { if (n & 1)p = (p % m * a % m) % m; a = (a % m * a % m) % m; n >>= 1; }return p; }
template<typename T> T exp(T a, T n){T p = 1; while (n) { if (n & 1)p *= a; a *= a;  n >>= 1; }return p;}
template<typename T> T invm(T a, T m) {return exp(a, m - 2, m);}
const int lim = 12e4+5;
int n;
pdd a[lim];
pdd hull[lim];
int head;
double cross_prod(pdd src, pdd a, pdd b)
{
	return (a.first - src.first) * (b.second - src.second) - (a.second - src.second) * (b.first - src.first);
}
bool cmp(pdd& b, pdd& c)
{
	return cross_prod(a[1], b, c)<0;
}
void getHull()
{
	hull[1] = a[1], hull[2] = a[2];
	head = 2;
	for (int i = 3; i <= n; i++)
	{
		while(head >= 2 && (cross_prod(hull[head - 1], hull[head], a[i]) > 0))
			head--;
		hull[++head] = a[i];
	}
}
int main()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);

	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].first >> a[i].second;
	int pos = 1;
	for (int i = 2; i <= n; i++)
		if (a[i] < a[pos])
			pos = i;
	swap(a[1], a[pos]);	
	sort(a + 2, a + n + 1, cmp);
	getHull();
	cout << head << '\n';
	for(int i=1;i<=head;i++)
		cout <<fixed<<setprecision(12)<< hull[i].first<<" "<<hull[i].second<<'\n';
}