Cod sursa(job #1765771)

Utilizator dani_mocanuDani Mocanu dani_mocanu Data 26 septembrie 2016 23:12:29
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <algorithm>

using namespace std;
const int nmax = 120005;
const double eps = 0.000000000001;
int N,st[nmax],fr[nmax],top;


struct Pct
{
    double x,y;
    bool operator < (const Pct &A) const
    {
        return y < A.y;
    }
};
Pct v[nmax];

inline double Prod(Pct A, Pct B, Pct C)
{
    return C.x*(B.y - A.y) + C.y*(A.x - B.x) + A.y*(B.x - A.x) - A.x*(B.y - A.y);
}


int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int i,semn;
    scanf("%d",&N);
    for(i = 1; i <= N; i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+N+1);
    top = 2;
    st[1] = 1, st[2] = 2;
    fr[2] = semn = 1;
   for(i = 3; i; i+=semn)
    {
        while(top >= 2 && Prod(v[st[top-1]],v[st[top]],v[i]) <= eps)
        {
            fr[top]--;
            top--;
        }
        st[++top] = i;
        fr[top]++;
        if(st[top] == N) semn = -1;
    }
    top--;
    printf("%d\n",top);
    for(i = 1; i <= top; i++)
        printf("%lf %lf\n",v[i].x ,v[i].y);
    return 0;
}