Cod sursa(job #2110859)

Utilizator vancea.catalincatalin vancea.catalin Data 21 ianuarie 2018 14:23:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 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);

struct punct{
	double x,y;
} v[DN], r[DN];

int n, ind;
double mx=INF, my=INF;


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

bool cmp(punct a, punct b)
{
	if(det(v[1], a, b)<=0) return 1; //?
	return 0;
}

int main()
{
	int i,lr;
	double x, y;
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x>>y;
		v[i]={x, y};
		if(mx>x || (mx==x && my>y)){
			ind=i; mx=x; my=y;
		}
	}
	v[n+1]=v[1];
	v[1]=v[ind];
	v[ind]=v[n+1];
	sort(v+2,v+n+1,cmp);
	r[1]=v[1]; lr=1;	
	
	for(i=2;i<=n;i++)
	{
		while(lr>1 && det(r[lr-1], r[lr], v[i])>0) lr--;
		r[++lr]=v[i];	
	}
	fout<<fixed<<lr<<"\n";
	for(i=lr;i>0;i--)
	{
		fout<<setprecision(12)<<r[i].x<<" "<<r[i].y<<"\n";
	}
}