Cod sursa(job #2110219)

Utilizator vancea.catalincatalin vancea.catalin Data 20 ianuarie 2018 13:14:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<stack>
#include<iomanip>

#define INF 1100000000
#define DN 120100
using namespace std;
fstream fin("infasuratoare.in",ios::in),fout("infasuratoare.out",ios::out);
struct puncte
{
	double x,y;
} v[DN];

int n,ind,ap[DN],lst;
double xm=INF,ym=INF;
puncte st[DN];

bool cmp(puncte a,puncte b)
{
	if(a.x<b.x) return 1;
	if(a.x==b.x && a.y<b.y) return 1;
	return 0;
}

int det(puncte a,puncte b,puncte c)
{
	double xx=0;
	xx=a.x*b.y+b.x*c.y+a.y*c.x;
	xx=xx-c.x*b.y-a.y*b.x-a.x*c.y;
	if(xx>0) return 1;
	if(xx<0) return -1;
	return 0;
}

int main()
{
	int i,k;
	double x,y;
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x>>y;
		v[i]={x,y};
	}
	sort(v+1,v+n+1,cmp);
	st[1]=v[1];
	lst=1;
	for(i=2;i<=n;i++)
	{
		while(lst>1 && det(st[lst-1],st[lst],v[i]) > 0)
		{
			lst--;
		}
		lst++;
		st[lst]=v[i];
	}
	k=lst;
	for(i=n-1;i>=1;i--)
	{
		while(lst>k && det(st[lst-1],st[lst],v[i]) > 0)
		{
			lst--;
		}
		lst++;
		st[lst]=v[i];
	}
	lst--;
	fout<<lst<<"\n";
	for(i=lst;i>0;i--) fout<<fixed<<setprecision(12)<<st[i].x<<" "<<st[i].y<<"\n";
	
	
}