Cod sursa(job #2065335)

Utilizator Andrei_Info1Ionescu Andrei Andrei_Info1 Data 13 noiembrie 2017 18:33:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1.e-14;
struct POINT
{
    double x,y;
}ll;
int ccw(const POINT &A, const POINT &B, const POINT &C)
{
    double cp = (B.x -A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.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 MyComp
{
    public:
            bool operator () (const POINT &A, const POINT &B)
            {
                int cp;
                double d1, d2;
                cp = ccw(ll, A, B);
                if(cp==0)
                {
                    d1=dist(ll,A);
                    d2=dist(ll,B);
                    if(d1 - d2 <= -eps)
                        return 1;
                    else
                        return 0;
                }
                if(cp==-1)
                    return 0;
                return 1;
            }
};
const int N=120000;

POINT P [N+10];
int H [N+10];
int n;
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int i, poz, u, cp;
    POINT aux;
    scanf("%d", &n);
    ll.x = ll.y = 1000000000;
    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;
        }
    }
    aux=P[0];
    P[0]=P[poz];
    P[poz]=aux;
    sort(P+1 , P+n , MyComp ());
    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("%.6f %.6f\n", P[H[i]].x, P[H[i]].y);
    return 0;
}