Cod sursa(job #2366823)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 4 martie 2019 22:23:03
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
const int NMAX=1e5+5;
struct punct {
	double x,y;
};
int n;
punct P[NMAX];
vector <punct> hull;
bool det(punct A,punct B,punct C)
{
	return ((A.x*(B.y-C.y)+B.x*(C.y-A.y)+C.x*(A.y-B.y))<0);
}
int cmp(punct A,punct B)
{
	if(A.x<B.x) return 1;
	if(A.x>B.x) return 0;
	return A.y<B.y;
}
int main()
{
	fi>>n;
	for(int i=1;i<=n;i++)
		fi>>P[i].x>>P[i].y;
	sort(P+1,P+n+1,cmp);
	hull.push_back(P[1]);
	hull.push_back(P[2]);
	for(int i=3;i<=n;i++)
	{
		while(hull.size()>1 && det(hull[hull.size()-2],hull[hull.size()-1],P[i]))
			hull.pop_back();
		hull.push_back(P[i]);
	}
	for(int i=n-1;i>0;i--)
	{
		while(hull.size()>1 && det(hull[hull.size()-2],hull[hull.size()-1],P[i]))
			hull.pop_back();
		hull.push_back(P[i]);
	}
	hull.pop_back();
	fo<<hull.size()<<"\n";
	for(int i=0;i<hull.size();i++)
		fo<<fixed<<setprecision(12)<<hull[i].x<<" "<<hull[i].y<<"\n";
	fi.close();
	fo.close();
	return 0;
}