Cod sursa(job #690150)

Utilizator andu04Popa Andi andu04 Data 25 februarie 2012 11:53:09
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <stdio.h>
#define INF 0x3f3f3f
#define NMAX 120001
using namespace std;

int n;
struct puncte{
    double x,y,pante;
};
puncte a[NMAX];
double pxmin,pymin;
int pozmin;
int stiva[NMAX],nr;
double calcularepanta(int xx)
{
    if (a[0].x==a[xx].x)
        return INF;
    return ((a[xx].y-a[0].y)/(a[xx].x-a[0].x));


}



void citire()
{

    freopen("infasuratoare.in","r",stdin);

    scanf("%d",&n);
    scanf("%lg%lg",&a[1].x,&a[1].y);
    pxmin=a[1].x;
    pymin=a[1].y;pozmin=1;
    for (int i=2;i<=n;++i)
    {
        scanf("%lg%lg",&a[i].x,&a[i].y);
        if (a[i].x<pxmin)
            pxmin=a[i].x,pymin=a[i].y,pozmin=i;
        else if (a[i].x==pxmin && a[i].y<pymin)
            pxmin=a[i].x,pymin=a[i].y,pozmin=i;
    }
    a[0].x=pxmin;
    a[0].y=pymin;
    a[pozmin].x=a[n].x;
    a[pozmin].y=a[n].y;
    --n;
    for (int i=1;i<=n;++i)
        a[i].pante=calcularepanta(i);
    puncte aux;
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
            if (a[i].pante>a[j].pante)
            {
               aux=a[i];
               a[i]=a[j];
               a[j]=aux;
            }

}
double determinant(int x1,int y1,int z1)
{
    double s1=0;
    s1+=(a[x1].x*a[y1].y);s1+=(a[y1].x*a[z1].y);s1+=(a[x1].y*a[z1].x);
    s1-=(a[y1].y*a[z1].x);s1-=(a[x1].x*a[z1].y);s1-=(a[y1].x*a[x1].y);
    return s1;

}

void rezolvare()
{

    stiva[0]=0;
    stiva[1]=1;
    nr=1;
    for (int i=2;i<=n;i++)
    {

        if (determinant(stiva[nr-1],stiva[nr],i)>=0)
            stiva[++nr]=i;
        else
        {
            while (determinant(stiva[nr-1],stiva[nr],i)<0)
            {
                nr--;
            }
            stiva[++nr]=i;
        }
    }
    printf("%d\n",nr+1);
    for (int i=0;i<=nr;i++)
        printf("%.4lf %.4lf\n",a[stiva[i]].x,a[stiva[i]].y);


}

int main()
{
    citire();
    freopen("infasuratoare.out","w",stdout);
    rezolvare();
    return 0;
}