Cod sursa(job #1279456)

Utilizator dr_personalityEftime Andrei Horatiu dr_personality Data 30 noiembrie 2014 13:38:45
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct punct{
	double x, y;
};

const int nmax = 120006;
int n, lst, pozfirst;
punct v[nmax], first, st[nmax];

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

bool compar(punct a, punct b)
{
	return (det(a, first, b)>0);
}

int main(){
	int player_unu=0;

	first.x = 100000000000;
	first.y = 100000000000;

	in>>n;
	for(int i = 0; i<n; i++)
	{
		in>>v[i].x>>v[i].y;

		if(v[i].x==first.x && v[i].y<first.y)
		{
			first = v[i];
			pozfirst = i;
		}
		if(v[i].x<first.x)
		{
			first = v[i];
			pozfirst = i;
		}
	}

	swap(v[pozfirst], v[0]);
	sort(v + 1, v + n, compar);

	st[0] = first;
	lst = 1;

	for(int i = 1; i<n; i++)
	{
		while(lst>1 && det(st[lst], st[lst - 1], v[i])>=0)
			lst--;

		st[lst] = v[i];
		lst++;
	}

	out<<lst<<'\n';
	out<<setprecision(6)<<fixed;
	for(int i = 0; i<lst; i++)
		out<<st[i].x<<' '<<st[i].y<<'\n';

	return player_unu;
}