Cod sursa(job #2556976)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 25 februarie 2020 13:31:07
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
// fara puncte coliniare!
#define NMAX 120005
#include <cstdio>
#include <algorithm>
using namespace std;


struct point{
    double x, y;

    bool operator>(const point &other) const {

    }
}P[NMAX], P0;

int n;
point S[NMAX];
int head;


int orientation(point A, point B, point C)
{
    double determinant = ((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));
    return determinant;
}



void read()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lf %lf", &P[i].x, &P[i].y);
}

void findP0()
{
    int pozP0 = 1;
    P0 = P[1];
    for(int i = 2; i <= n; ++i)
        if(P[i].y < P[pozP0].y || (P[i].y == P[pozP0].y && P[i].x < P[pozP0].x))
            pozP0 = i;
    swap(P[pozP0], P[1]);
    P0 = P[1];
}

bool cmp(point B, point C)
{
    return (orientation(P0, B, C) > 0);
}



void sortPoints()
{
    findP0();
    sort(P+2, P+n+1, cmp);

}


void infasuratoare()
{
    S[1] = P0;
    S[2] = P[2];
    head = 2;

    for(int i = 3; i <= n; ++i)
    {
        while(head >= 2 && orientation(S[head-1], S[head], P[i]) < 0)
            --head;
        S[++head] = P[i];
    }
}

void afis()
{
    printf("%d\n", head);
    for(int i = 1; i <= head; ++i)
        printf("%.9f %.9f\n", S[i].x, S[i].y);
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    read();
    sortPoints();
    infasuratoare();
    afis();
    return 0;
}