Cod sursa(job #1125481)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 26 februarie 2014 17:53:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<cstdio>
#include<algorithm>
#define x first
#define y second
#define point pair<double,double>
using namespace std;
const int nmax = 120005;
int n,i,aux,st[nmax],m;
point p[nmax];
double cp(const point &a,const point &b,const point &c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
}
bool cmp(const point &a,const point &b)
{
    return cp(p[1],a,b)<0;
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n); aux=1;
	for(i=1;i<=n;i++)
	{
	    scanf("%lf%lf",&p[i].x,&p[i].y);
	    if(p[i]<p[aux]) aux=i;
	}
	swap(p[1],p[aux]);
	sort(p+2,p+n+1,cmp);
	for(i=1;i<=n;i++)
	{
	    while(m>=2 && cp(p[st[m-1]],p[st[m]],p[i])>0) m--;
	    st[++m]=i;
	}
	printf("%d\n",m);
	for(i=m;i;i--) printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);
	return 0;
}