Cod sursa(job #713599)

Utilizator mihai995mihai995 mihai995 Data 14 martie 2012 19:40:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=120005;
struct punct{double x,y;} v[N],a[N],b[N];
int A,B,n;

ifstream in("infasuratoare.in");

inline bool cmp(const punct &a,const punct &b)
{
    return a.x<b.x || a.x==b.x && a.y<b.y;
}

inline bool panta(punct a,punct b,punct c)
{
    return (b.y-a.y)*(c.x-a.x)<(b.x-a.x)*(c.y-a.y);
}

int main()
{
    freopen("infasuratoare.out","w",stdout);
    int i;
    in>>n;
    for (i=1;i<=n;i++)
        in>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    a[++A]=v[1];
    for (i=2;i<=n;i++)
    {
        while (A>1 && panta(a[A-1],a[A],v[i]))
            A--;
        a[++A]=v[i];
    }
    A--;
    b[++B]=v[n];
    for (i=n-1;i;i--)
    {
        while (B>1 && panta(b[B-1],b[B],v[i]))
            B--;
        b[++B]=v[i];
    }
    B--;
    printf("%d\n",A+B);
    for (i=B;i;i--)
        printf("%.6lf %.6lf\n",b[i].x,b[i].y);
    for (i=A;i;i--)
        printf("%.6lf %.6lf\n",a[i].x,a[i].y);
    return 0;
}