Cod sursa(job #1111232)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 18 februarie 2014 18:43:03
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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,s,t,cnt,cnt2;
point p[nmax],a[nmax],b[nmax],sol[nmax],sol2[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;
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p+1,p+n+1);
    for(i=2;i<n;i++) if(cp(p[1],p[n],p[i])>0) a[++s]=p[i]; else b[++t]=p[i];
    sol[++cnt]=p[1];
    for(i=1;i<=t;i++)
    {
        while(cnt>=2 && cp(sol[cnt-1],sol[cnt],b[i])<0) cnt--;
        sol[++cnt]=b[i];
    }
    sol2[++cnt2]=p[n];
    for(i=s;i;i--)
    {
        while(cnt2>=2 && cp(sol2[cnt2-1],sol2[cnt2],a[i])<0) cnt2--;
        sol2[++cnt2]=a[i];
    }
    printf("%d\n",cnt+cnt2);
    for(i=1;i<=cnt;i++) printf("%lf %lf\n",sol[i].x,sol[i].y);
    for(i=1;i<=cnt2;i++) printf("%lf %lf\n",sol2[i].x,sol2[i].y);
	return 0;
}