Cod sursa(job #2119247)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 31 ianuarie 2018 20:47:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point
{
	double x;
	double y;
};

double cross(point o,point a,point b)
{
	return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}

bool wayToSort(point lh,point rh)
{
	if(lh.x==rh.x)	return lh.y<rh.y;
	else return lh.x<rh.x;
}

vector <point> p;
vector <point> l;
vector <point> u;
vector <point> raspuns;
int nr;

int main()
{
	point foo;
	fin>>nr;
	for(int i=0;i<nr;i++)
	{
		fin>>foo.x>>foo.y;
		p.push_back(foo);
	}
	sort(p.begin(),p.end(),wayToSort);
	fout<<setprecision(12)<<fixed;

	for(int i=0;i<nr;i++)
	{
		while(u.size()>=2&&cross(u.back(),u[u.size()-2],p[i])<=0)
			u.pop_back();
		u.push_back(p[i]);
	}
	for(int i=nr-1;i>=0;i--)
	{
		while(l.size()>=2&&cross(l.back(),l[l.size()-2],p[i])<=0)
			l.pop_back();
		l.push_back(p[i]);
	}
	u.pop_back();
	l.pop_back();
	raspuns=u;
	raspuns.insert(raspuns.end(),l.begin(),l.end());
	//sort(raspuns.begin(),raspuns.end(),wayToSort);
	fout<<raspuns.size()<<"\n";
	for(int i=raspuns.size()-1;i>=0;i--)
	{
		fout<<raspuns[i].x<<" "<<raspuns[i].y<<"\n";
	}
	return 0;
}