Cod sursa(job #291102)

Utilizator Mishu91Andrei Misarca Mishu91 Data 29 martie 2009 13:26:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX_N 120005

struct punct
{
   double x, y;
} P[MAX_N];

int N, i, p, vf;
int St[MAX_N];

void swap(int i, int j)
{
    punct aux;
         
    aux = P[i]; P[i] = P[j]; P[j] = aux;
}

struct cmp
{
    bool operator ()(const punct &A, const punct &B) const
    {
        return (double) (A.x-P[1].x)*(B.y-P[1].y) > (double) (B.x-P[1].x)*(A.y-P[1].y);
    }
};
     
int sign(int i, int j, int k)
{
    double x1, y1;
         
    x1 = (P[i].x - P[k].x) * (P[j].y - P[k].y);
    y1 = (P[j].x - P[k].x) * (P[i].y - P[k].y);
         
    return (x1 - y1 > 0);
}

void citire()
{
    scanf("%d",&N);
    for (i = 1, p = 1; i <= N; ++i)
    {
        scanf("%lf %lf",&P[i].x ,&P[i].y);
        if (P[i].x < P[p].x) p = i;
        if (P[i].x ==P[p].x && P[i].y < P[p].y) p = i;
    }
         
    swap(1,p);
}

void solve()
{
    sort(P+2, P+N+1, cmp());
         
    St[vf = 1] = 1;
    for (i = 2; i <= N; ++i)
    {
        while (vf >= 2 && sign(St[vf-1], St[vf], i) < 1) --vf;
        St[++vf] = i;
    }
         
    printf("%d\n",vf);
    for (i = 1; i <= vf; ++i)
        printf("%lf %lf\n",P[St[i]].x, P[St[i]].y);
}

int main()
{
    freopen("infasuratoare.in","rt",stdin);
    freopen("infasuratoare.out","wt",stdout);

    citire();
    solve();
}