Cod sursa(job #1014668)

Utilizator misu007Pogonaru Mihai misu007 Data 22 octombrie 2013 23:53:54
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.73 kb
#include <cstdio>
using namespace std;

long double a[120000][3];
int r[120000];

void qs(int stanga, int dreapta)
{
   int i, j;
   long double mijloc, aux;         // variabilele
   i=stanga;                       //  initializarea
   j=dreapta;                    //   indicilor
   mijloc=a[(stanga+dreapta)/2][2];  // initializarea variabilei - pivot
  while(i<=j)
  {
   while(a[i][2]<mijloc)  // apropierea i-ului de mijloc
      i++;
   while(a[j][2]>mijloc)   // apropierea j-ului de mijloc
      j--;
    if(i<=j)   //conditia efectuarii operatiei de interschimbare
    {
       aux=a[i][2];
       a[i][2]=a[j][2];   // operatia de interschimbare
       a[j][2]=aux;
       aux=a[i][1];
       a[i][1]=a[j][1];   // operatia de interschimbare
       a[j][1]=aux;
       aux=a[i][0];
       a[i][0]=a[j][0];   // operatia de interschimbare
       a[j][0]=aux;
       i++;
       j--;
     }
  }
 if(stanga<j)                    //recursivitatea
   qs(stanga, j);   // in partea stanga
 if(i<dreapta)
   qs(i, dreapta);  // in partea dreapta

}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int i,k,n;
    long double x,y,z;
    scanf("%d",&n);
    scanf("%Lf%Lf",&a[0][0],&a[0][1]);
    r[0]=0;
    for(i=1;i<n;++i)
    {
        scanf("%Lf%Lf",&a[i][0],&a[i][1]);
        if(a[r[0]][0]>a[i][0]) r[0]=i;
    }
    for(i=0;i<r[0];++i)
    {
        a[i][2]=(a[i][1]-a[r[0]][1])/(a[i][0]-a[r[0]][0]);
    }
    for(i=r[0]+1;i<n;++i)
    {
        a[i][2]=(a[i][1]-a[r[0]][1])/(a[i][0]-a[r[0]][0]);
    }
    x=a[r[0]][0];
    a[r[0]][0]=a[0][0];
    a[0][0]=x;
    x=a[r[0]][1];
    a[r[0]][1]=a[0][1];
    a[0][1]=x;
    r[0]=0;
    qs(1,n-1);
    r[1]=1;
    y=a[1][2];
    x=(a[1][0]-a[0][0])*(a[1][0]-a[0][0])+(a[1][1]-a[0][1])*(a[1][1]-a[0][1]);
    i=2;
    while(a[i][2]==y)
    {
        z=(a[i][0]-a[0][0])*(a[i][0]-a[0][0])+(a[i][1]-a[0][1])*(a[i][1]-a[0][1]);
        if(z>x)
        {
            x=z;
            r[1]=i;
        }
        ++i;
    }
    x=a[r[1]][0];
    a[r[1]][0]=a[1][0];
    a[1][0]=x;
    x=a[r[1]][1];
    a[r[1]][1]=a[1][1];
    a[1][1]=x;
    k=2;
    for(i=2;i<n;++i)
    {
        r[k]=i;
        x=a[k][1]-a[k-2][1];
        y=a[k-2][0]-a[k][0];
        z=-a[k-2][0]*x-a[k-2][1]*y;
        while(k>2&&((x*a[0][0]+y*a[0][1]+z)*(x*a[k-1][0]+y*a[k-1][1]+z)>=0))
        {
            r[k-1]=r[k];
            --k;
            x=a[k][1]-a[k-2][1];
            y=a[k-2][0]-a[k][0];
            z=-a[k-2][0]*x-a[k-2][1]*y;
        }
        ++k;
    }
    printf("%d\n",k);
    for(i=0;i<k;++i)
    {
        printf("%Lf %Lf\n",a[r[i]][0],a[r[i]][1]);
    }
    return 0;
}