Cod sursa(job #1164122)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 1 aprilie 2014 21:01:14
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<cstdio>
#include<algorithm>
#define point pair<double,double>
#define x first
#define y second
using namespace std;
const int nmax = 120005;
int n,i,m,st[nmax],top;
point p[nmax];
double cp(point a,point b,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;
}
struct cmp
{
    bool operator () (point a,point b) const
    {
        return cp(p[1],a,b)>0;
    }
};
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n); m=1;
	for(i=1;i<=n;i++)
	{
	    scanf("%lf%lf",&p[i].x,&p[i].y);
	    if(p[i]<p[m]) m=i;
    }
    sort(p+2,p+n+1,cmp());
    for(i=1;i<=n;i++)
    {
        while(top>=2 && cp(p[i],p[st[top]],p[st[top-1]])>0) top--;
        st[++top]=i;
    }
    printf("%d\n",top);
    for(i=1;i<=top;i++) printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);
	return 0;
}