Cod sursa(job #2110558)

Utilizator vancea.catalincatalin vancea.catalin Data 20 ianuarie 2018 21:10:21
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<algorithm>
#include<iostream>
#include<fstream>
#include<iomanip>
#define INF 1999999999
#define DN 120100

using namespace std;
fstream fin("infasuratoare.in",ios::in), fout("infasuratoare.out",ios::out);
int n,k,lst;
struct punct
{
	double x, y;
} v[DN],st[DN];

bool cmp(punct a, punct b)
{
	if(a.x<=b.x) return 1;
	return 0;	
}
int det(punct a, punct b, punct c)
{
	double x;
	x=a.x*b.y+b.x*c.y+a.y*c.x;
	x=x-c.x*b.y-a.y*b.x-c.y*a.x;
	if(x<0) return -1;
	if(x>0) return 1;
	return 0;
}
int main()
{
	int i;
	double a, b;
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>a>>b;
		v[i]={a, b};
	}
	
	sort(v+1,v+n+1,cmp);
	st[lst=1]=v[1];
	for(i=1;i<=n;i++)
	{
		while(lst>1 && det(st[lst-1],st[lst], v[i])<=0) lst--;
		st[++lst]=v[i];
	}
	k=lst;
	for(i=n;i>=1;i--)
	{
		while(lst>k && det(st[lst-1],st[lst], v[i])<=0) lst--;
		st[++lst]=v[i];
	}
	fout<<fixed;
	fout<<lst-1<<"\n";
	for(i=1;i<lst;i++)
	{
		fout<<st[i].x<<" "<<st[i].y<<"\n";
	}
}