Cod sursa(job #1529467)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 20 noiembrie 2015 22:25:50
Problema Infasuratoare convexa Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 1.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct punct
{
    double x,y;
}v[120001];
int stiva_down[120001],f[120001],stiva_up[120001];
int angle_down(int a,int o,int b)
{
    if(v[o].y<v[a].y || v[o].y<v[b].y)
        return 1;
    return 0;
}
int angle_up(int a,int o,int b)
{
    if(v[o].y>v[a].y || v[o].y>v[b].y)
        return 1;
    return 0;
}
void quicksort(int p,int u)
{
    int j,i;
    double pivot,aux;
    if(p<u)
    {
        pivot=v[(p+u)/2].x;
        i=p;
        j=u;
        while(i<=j)
        {
            while(v[i].x<pivot && i<u)
                i++;
            while(v[j].x>pivot && j>p)
                j--;
            if(i<=j){
                aux=v[i].x;
                v[i].x=v[j].x;
                v[j].x=aux;
                if((v[i].y>v[j].y && v[j].x==v[i].x) || v[j].x>v[i].x)
                {
                    aux=v[i].y;
                    v[i].y=v[j].y;
                    v[j].y=aux;
                }
                i++;
                j--;
            }
        }
        if(p<j)
            quicksort(p,j);
        if(i<u)
            quicksort(i,u);
    }
}
int main()
{
    int n,i,d,u;
    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);
    quicksort(1,n);
    stiva_down[1]=1;
    d=1;
    for(i=2; i<=n; i++)
    {
        while(d>1 && !angle_down(stiva_down[d-1],stiva_down[d],i))
            d--;
        stiva_down[++d]=i;
    }
    stiva_up[1]=1;
    u=1;
    for(i=2; i<=n; i++)
    {
        while(u>1 && !angle_up(stiva_up[u-1],stiva_up[u],i))
            u--;
        stiva_up[++u]=i;
    }
    printf("%d\n",u+d-2);
    for(i=1; i<=d; i++)
        printf("%.6lf %.6lf\n",v[stiva_down[i]].x,v[stiva_down[i]].y);
    for(i=u-1; i>1; i--)
        printf("%.6lf %.6lf\n",v[stiva_up[i]].x,v[stiva_up[i]].y);

    return 0;
}