Cod sursa(job #1529660)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 21 noiembrie 2015 10:07:26
Problema Infasuratoare convexa Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.86 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct punct
{
    double x,y;
}v[120001];
int stiva[120001],f[120001];
long double determinant(int A,int C,int B) {
  return (long double)v[A].x * v[B].y
      + (long double)v[B].x * v[C].y
      + (long double)v[C].x * v[A].y
      - (long double)v[C].x * v[B].y
      - (long double)v[A].x * v[C].y
      - (long double)v[B].x * v[A].y;
}
void quicksort(int p,int u)
{
    int j,i;
    long 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[1]=1;
    u=1;
    for(i=2; i<=n; i++)
    {
        while(u>1 && determinant(stiva[u-1],stiva[u],i)<=0.0)
            u--;
        stiva[++u]=i;
    }
    for(i=n-1; i>=1; i--)
    {
        while(u>1 && determinant(stiva[u-1],stiva[u],i)<=0.0)
            u--;
        stiva[++u]=i;
    }
    printf("%d\n",u-1);
    for(i=u; i>1; i--)
        printf("%.6lf %.6lf\n",v[stiva[i]].x,v[stiva[i]].y);

    return 0;
}