Cod sursa(job #930820)

Utilizator tudy23Coder Coder tudy23 Data 27 martie 2013 20:37:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=120100;
struct pt
{
    double x,y;
}x[N],h[N];
int k,n;
bool cmp(pt x1, pt x2)
{
    if(x1.x<x2.x)
        return true;
    if(x1.x==x2.x)
        if(x1.y<x2.y)
            return true;
    return false;
}
void citire()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&x[i].x,&x[i].y);
    fclose(stdin);
}
inline double ccw(pt x1, pt x2, pt x3)
{
    return (x2.x-x1.x)*(x3.y-x1.y) - (x2.y-x1.y)*(x3.x-x1.x);
}
void hull()
{
    for(int i=1;i<=n;++i)
    {
        while(k>=2&&ccw(h[k-2],h[k-1],x[i])<=0) --k;
        h[k++]=x[i];
    }
    for(int i=n-1,t=k+1;i>=0;--i)
    {
        while(k>=t&&ccw(h[k-2],h[k-1],x[i])<=0) k--;
        h[k++]=x[i];
    }
    k--;
}
void afisare()
{
    freopen("infasuratoare.out","w",stdout);
    printf("%d\n",k);
    for(int i=0;i<k;++i)
        printf("%lf %lf\n",h[i].x,h[i].y);
    fclose(stdout);
}
int main()
{
    citire();
    sort(x+1,x+n+1,cmp);
    hull();
    afisare();
    return 0;
}