Cod sursa(job #2110090)

Utilizator anisca22Ana Baltaretu anisca22 Data 20 ianuarie 2018 12:24:49
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define NMAX 120005

using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct hull
{
    double x, y;
    bool operator < (const hull &other)const{
        if (x == other.x)return y < other.y;
        return x < other.x;
    }
}pct[NMAX];

int N, top;
int st[NMAX];

double det(int A, int B, int C)
{
    /**
    A x y 1
    B x y 1
    C x y 1
    **/
    return (pct[A].x * pct[B].y) + (pct[A].y * pct[C].x) + (pct[B].x * pct[C].y)
            - (pct[C].x * pct[B].y) - (pct[C].y * pct[A].x) - (pct[B].x * pct[A].y);
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; i++)
        fin >> pct[i].x >> pct[i].y;
    sort(pct + 1, pct + N + 1);
    st[1] = 1;
    top = 1;
    ///det < 0 => stanga
    ///det = 0 => coliniare
    ///det > 0 => dreapta
    for (int i = 2; i <= N; i++)
    {
        while (top >= 2 && det(st[top - 1], st[top], i) >= 0)
            --top;
        st[++top] = i;
    }
    for (int i = N - 1; i >= 1; i--)
    {
        while (top >= 2 && det(st[top - 1], st[top], i) >= 0)
            --top;
        st[++top] = i;
    }
    top--;
    fout << top << "\n";
    for (int i = 1; i <= top; i++)
        fout << fixed << setprecision(12) << pct[st[i]].x << " " << pct[st[i]].y << "\n";
    return 0;
}