Cod sursa(job #2089459)

Utilizator cyg_ieeuVasile Radu-Andrei cyg_ieeu Data 16 decembrie 2017 16:02:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <climits>

using namespace std;
struct point
{
    double x,y;
};
const double eps = 1.e-14;
point ll;
int ccw(const point &p1,const point &p2,const point &p3)
{
    double 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;
}
double dist(const point &a,const point &b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
class cmp
{
    public:
        bool operator () (const point &p1,const point &p2)
        {
            int cp;
            double d1,d2;
            cp = ccw(ll,p1,p2);
            if(cp == 0)
            {
                d1 = dist(ll,p1);
                d2 = dist(ll,p2);
                if(d1 - d2 <= -eps)
                    return 1;
                else
                    return 0;
            }
            if(cp == -1)
                return 0;
            return 1;
        }
};
point p[120005];
int h[120005];
int n;
int main()
{
    freopen("infasuratoare.in", "r",stdin);
    freopen("infasuratoare.out", "w",stdout);
    int i,u,cp,poz;
    scanf("%d", &n);
    ll.x = ll.y = INT_MAX;
    for(i = 0;i < n;i++)
    {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if(p[i].y - ll.y <= -eps || (fabs(p[i].y - ll.y) < eps && p[i].x - ll.x <= -eps))
        {
            ll = p[i];
            poz = i;
        }
    }
    swap(p[0],p[poz]);
    sort(p + 1,p + n,cmp());
    p[n] = p[0];
    h[1] = 0;
    h[2] = 1;
    i = 2;
    u = 2;
    while(i <= n)
    {
        cp = ccw(p[h[u - 1]],p[h[u]],p[i]);
        if(cp > 0)
        {
            h[++u] = i;
            ++i;
        }
        else
            u--;
    }
    u--;
    printf("%d\n",u);
    for(i = 1;i <= u;i++)
        printf("%.6lf %.6lf\n",p[h[i]].x,p[h[i]].y);
    return 0;
}