Cod sursa(job #729921)

Utilizator mihai995mihai995 mihai995 Data 31 martie 2012 00:55:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int N=100005;
int stack[N],n;
bool use[N];
struct Punct
{
    double x,y;
} a[N];

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

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

inline void print(Punct &x)
{
    out<<x.x<<" "<<x.y<<"\n";
}

inline int cross(Punct A,Punct B,Punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

void del(Punct &C)
{
    while (stack[0]>1 && cross(a[stack[stack[0]-1]],a[stack[stack[0]]],C)<0)
        use[stack[stack[0]--]]=false;
}

void convex_hull()
{
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++)
    {
        del(a[i]);
        stack[++stack[0]]=i;
        use[i]=true;
    }
    for (int i=n;i;i--)
    {
        if (use[i])
            continue;
        del(a[i]);
        stack[++stack[0]]=i;
        use[i]=true;
    }
}

int main()
{
    in>>n;
    for (int i=1;i<=n;i++)
        in>>a[i].x>>a[i].y;
    convex_hull();
    out<<stack[0]<<"\n";
    for (int i=1;i<=stack[0];i++)
        print(a[stack[i]]);
    return 0;
}