Cod sursa(job #2628261)

Utilizator chiravladChira Vlad chiravlad Data 15 iunie 2020 11:50:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
const double eps=1.0e-12;

struct POINT
{
    double x, y;
};

POINT p[120005];

int ccw(POINT p1, POINT p2, POINT p3)
{
    double cp;
    cp = (p2.x-p1.x) * (p3.y - p2.y) - (p2.y-p1.y)*(p3.x-p2.x);
    if(fabs(cp) < eps)
        return 0;
    if(cp >= eps)
        return 1;
    return -1;
}

POINT ll;

bool cmp(POINT a, POINT b)
{
    if(a.x == ll.x && a.y == ll.y)
        return 1;
    if(b.x == ll.x && b.y == ll.y)
        return 0;
    return (ccw(ll, a, b) > 0);
}

int s[120005];
int top = 0;

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    scanf("%d",&n);
    scanf("%lf%lf",&p[1].x,&p[1].y);
    ll = p[1];
    for(int i = 2; i <= n; i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(p[i].x == ll.x)
        {
            if(p[i].y < ll.y)
                ll = p[i];
        }
        else if(p[i].x < ll.x)
        {
            ll = p[i];
        }
    }

    std::sort(p+1, p+n+1, cmp);

    for(int i = 1; i <= n; i++)
    {
        while(top >= 2 && ccw(p[s[top-1]], p[s[top]], p[i])<=0)
        {
            top--;
        }
        top++;
        s[top]= i;
    }

    while(top >= 2 && ccw(p[s[top-1]], p[s[top]], p[0])<=0)
    {
        top--;
    }
    top++;
    s[top]= 0;

    top--;

    printf("%d\n",top);

    for(int i = 1; i <= top; i++)
    {
        printf("%f %f\n",p[s[i]].x,p[s[i]].y);
    }

    return 0;
}