Cod sursa(job #690107)

Utilizator 1994Barbulescu Daniel 1994 Data 25 februarie 2012 11:01:24
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <cstdio>
#include <algorithm>
#define inf 1000000000
#define nMax 120010
using namespace std;

struct ceva{
    double x;
    double y;
    long double panta;

}a[nMax],stiva[nMax];

int n;
int nrPc;
int Xmin,Ymin;

bool cmp(ceva i,ceva j)
{
    return (i.panta<j.panta);
}

void read()
{
    Xmin=Ymin=1000000010;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lf %lf",&a[i].x,&a[i].y);
        if (Xmin>a[i].x)
        {
            Xmin=a[i].x;
            Ymin=a[i].y;
        }
        else
        if (Xmin==a[i].x)
            if(Ymin>a[i].y){
                Xmin=a[i].x;
                Ymin=a[i].y;
            }
    }
}

long double Panta(ceva i,ceva j)
{
    if (i.x==j.x)
        return inf;
    else
        return ((i.y-j.y)/(i.x-j.x));
}

void solve_panta()
{
    ceva aux;
    aux.x=Xmin;
    aux.y=Ymin;
    for (int i=1;i<=n;i++){
        if (!(a[i].x==Xmin && a[i].y==Ymin))
            a[i].panta=Panta(aux,a[i]);
        else
        if (a[i].x==Xmin && a[i].y==Ymin)
            a[i].panta=-inf;
    }
}

long double determinant(ceva A,ceva B,ceva C)
{
    return (A.x*B.y + A.y*C.x + B.x*C.y - B.y*C.x - C.y*A.x - A.y*B.x);
}

void solve()
{
    nrPc=0;
    stiva[++nrPc]=a[1];
    stiva[++nrPc]=a[2];
    for (int i=3;i<=n;i++)
    {
        if (determinant(stiva[nrPc-1],stiva[nrPc],a[i])>=0)
            stiva[++nrPc]=a[i];
        else{
            while (determinant(stiva[nrPc-1],stiva[nrPc],a[i])<0)
                nrPc--;
            //nrPc++;
            i--;
        }
    }
}

void print()
{
    printf("%d\n",nrPc);
    for (int i=1;i<=nrPc;i++)
        printf("%0.6lf %0.6lf\n",stiva[i].x,stiva[i].y);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    read();
    solve_panta();
    sort(a+1,a+n+1,cmp);
    solve();
    print();
    return 0;
}