Cod sursa(job #3148699)

Utilizator Raul_AArdelean Raul Raul_A Data 3 septembrie 2023 15:40:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define cin in
#define cout out
#define double long double
using namespace std;

const string file_name("infasuratoare");

ifstream in(file_name + ".in");
ofstream out(file_name + ".out");

struct Point{
	double x,y;
} v[150005], aux;

int n, vf, pos,s[150005];
double xmin, ymin = LLONG_MAX;

int comp(Point a, Point b){
	return a.x * b.y >= b.x * a.y;
}

bool convex (Point a, Point b, Point c)
{
	double rez = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
	return rez>0;
}

int main ()
{
	cin>>n;
	for (int i = 1 ; i <= n ; i++)
    {
		cin>>v[i].x>>v[i].y;
		if (ymin > v[i].y)
        {
			xmin = v[i].x;
			ymin = v[i].y;
			pos = i;	
		}
	}
	
	for (int i = 1 ; i <= n ; i++)
    {
		v[i].x -= xmin;
		v[i].y -= ymin;
	}
	
    swap(v[1],v[pos]);

	sort (v+2, v+n+1, comp); 
	
	
	s[1] = 1;
	s[2] = 2;
	vf = 2;
	
	for (int i = 3 ; i <= n ; i++)
    {
		while ( vf >= 3 and !convex(v[s[vf-1]], v[s[vf]], v[i]) )
			vf --;
		s[++vf] = i;
	}
	
	cout<<vf<<'\n';
	for (int i = 1 ; i <= vf ; i++) 
		cout<<fixed<<setprecision(10)<<v[s[i]].x + xmin<<' '<<v[s[i]].y + ymin<<'\n';	

	return 0; 
}