Cod sursa(job #2556960)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 25 februarie 2020 13:07:52
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 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));
    if(determinant < 0)
        return -1;
    if(determinant > 0)
        return 1;
    return 0;
}



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

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

void delP0()
{
    int i = 1;
    while(P[i].x != P0.x && P[i].y != P0.y)
       ++i;
    for(i; i <= n; ++i)
        P[i] = P[i+1];
    n--;
}

void sortPoints()
{
    findP0();
    delP0();

    for(int i=1; i<n; ++i)
        for(int j = i+1; j <= n; ++j)
            if(orientation(P0, P[i], P[j]) < 0)
                swap(P[j], P[i]);
}


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

    for(int i = 2; 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;
}