Cod sursa(job #1598043)

Utilizator Alexandru098Costea Vlad Alexandru098 Data 12 februarie 2016 16:18:59
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define infinity 2000000000
#define eps 1.0e-12

using namespace std;
int n,lli;
double x,y;
struct point
{
	double x,y;
};
point v[120005],aux;
vector<point> st;

int ccv(point p1,point p2,point p3)
{
	double cp=(p2.x-p1.x)*(p3.y-p2.y)-
						(p2.y-p1.y)*(p3.x-p2.x);
	if(cp>=eps) return 1;
	if(cp<=-eps) return -1;
	return 0;
}

int cmp(point a,point b)
{
	return ccv(v[1],a,b)>0;
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	v[0].x=v[0].y=infinity;
	for(int i=1;i<=n;i++)
	{
		scanf("%lf %lf",&x,&y);
		v[i].x=x;
		v[i].y=y;
		if((v[lli].y-v[i].y)>=eps)
			lli=i;
		else if((fabs(v[lli].y-v[i].y)<eps)&&(v[lli].x-v[i].x)>=eps)
			lli=i;
	}
	aux=v[lli];
	v[lli]=v[1];
	v[1]=aux;
	sort(v+2,v+n+1,cmp);
	n++;
	v[n]=v[1];
	st.push_back(v[1]);
	st.push_back(v[2]);
	for(int i=3;i<=n;i++)
	{
		while(ccv(st[st.size()-2],st[st.size()-1],v[i])<1)
			st.pop_back();
		st.push_back(v[i]);
	}
	printf("%d\n",st.size()-1);
	for(int i=0;i<st.size()-1;i++)
	{
		printf("%lf %lf\n",st[i].x,st[i].y);
	}
	return 0;
}