Cod sursa(job #883092)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 19 februarie 2013 18:41:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int n,i,j,k;
double a,b;
vector<int>s;
struct nod
{
	double x;
	double y;
}v[120005];
	
bool cmp(const nod a1,const nod b1)
{
	return (a1.y-b)*(b1.x-a)<=(a1.x-a)*(b1.y-b);
}

int semn(int a,int b,int c)
{
	double s=0;
	s=v[a].x*v[b].y+v[b].x*v[c].y+v[a].y*v[c].x-v[b].y*v[c].x-v[c].y*v[a].x-v[b].x*v[a].y;
	if (s<0) return 0;
	return 1;
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);a=999999999;b=999999999;
	for (i=1;i<=n;i++)
	{
		scanf("%lf %lf",&v[i].x,&v[i].y);
		if (a>v[i].x) a=v[i].x,b=v[i].y,k=i;else
			if (a==v[i].x && b>v[i].y) b=v[i].y,k=i;
	}
	swap(v[k],v[1]);
	sort(v+1,v+n+1,cmp);
	s.push_back(0);
	s.push_back(1);
	s.push_back(2);
	k=2;
	for (i=3;i<=n;i++)
	{
		while (k>=2 && !semn(s[k-1],s[k],i)) k--,s.pop_back();
		k++;
		s.push_back(i);
	}
	printf("%d\n",k);
	for(i=1;i<=k;i++)  printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
	return 0;
}