Cod sursa(job #1807237)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 16 noiembrie 2016 11:14:39
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define eps 1e-12
#define max_n 120001
//sursa test
int n,i,h;
typedef struct punct {
        double x,y;
};
punct p[max_n],v[max_n];
int s[max_n],ok[max_n];

inline int cmp1(double a,double b) {
        if (a+eps<b) return 1;
        if (b+eps<a) return -1;
        return 0;
}

bool cmp(const punct &a,const punct &b)
{
        int t;
        t=cmp1(a.x,b.x);
        if (t!=0) return t==1;
        return (cmp1(a.y,b.y)==1);
}

int semn(punct a,punct b,punct c)
{
        double A,B,C;
        A = a.y-b.y;
        B = b.x-a.x;
        C = a.x*b.y - b.x*a.y;
        return cmp1(A*c.x+B*c.y+C,0);
}

void rezolva() {
        int k,q;
        sort(v+1,v+n+1,cmp);
        s[1]=1; s[2]=2;
        ok[2]=1;
        k=2;
        i=3;
        q=1;
        while (!ok[1])
        {
                while (ok[i])
                {
                        if (i==n) q=-1;
                        i+=q;
                }
                while (k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1)
                {
                        ok[s[k--]]=0;
                }
                s[++k]=i;
                ok[i]=1;
        }
        h=k-1;

}

int main () {
        freopen("infasuratoare.in","r",stdin);
        freopen("infasuratoare.out","w",stdout);
        scanf("%d",&n);
        for (i=1; i<=n; i++)
                scanf("%lf%lf",&v[i].x,&v[i].y);
        rezolva();
        printf("%d\n",h);
        for (i=2; i<=h+1; i++)
                printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
        return 0;
}