Cod sursa(job #1686205)

Utilizator MihaiEMihaiE MihaiE Data 12 aprilie 2016 09:36:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <stdio.h>
#include <algorithm>
#define eps 1e-12
#define nmax 120010

using namespace std;

struct date { double x,y; };

int n,head;
int stiva[nmax];
bool fr[nmax];
date t[nmax];

inline double abss(double x) { if (x<eps) return (-x); else return x; }

bool cmp(const date &a,const date &b)
{
    if (abss(a.x-b.x)<=eps) return ((a.y-b.y)<=eps); else
        return ((a.x-b.x)<=eps);
}

double upperline(date a,date b,date c)
{
    return a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-c.y*a.x-a.y*b.x;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);

    for (int i=1;i<=n;i++) scanf("%lf %lf",&t[i].x,&t[i].y);

    sort(t+1,t+n+1,cmp);

    head=2; stiva[1]=1; stiva[2]=2; fr[2]=true;

    for (int i=3;i<=n;i++) {

        if (fr[i]) continue;

        while (head>=2 && upperline(t[stiva[head-1]],t[stiva[head]],t[i])>eps) fr[stiva[head]]=false,head--;

        head++; stiva[head]=i; fr[i]=true;

    }

    for (int i=n;i>=1;i--) {

        if (fr[i]) continue;

        while (head>=2 && upperline(t[stiva[head-1]],t[stiva[head]],t[i])>eps) fr[stiva[head]]=false,head--;

        head++; stiva[head]=i; fr[i]=true;

    }

    printf("%d\n",head-1);

    for (int i=head-1;i>=1;i--) printf("%f %f\n",t[stiva[i]].x,t[stiva[i]].y);

    return 0;
}