Cod sursa(job #2110162)

Utilizator anisca22Ana Baltaretu anisca22 Data 20 ianuarie 2018 12:47:38
Problema Infasuratoare convexa Scor 100
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 (y == other.y)return x < other.x;
        return y < other.y;
    }
}pct[NMAX];

int N, top;
int st[NMAX];

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

int cmp (hull A, hull B)
{
    return det(pct[1], A, B) >= 0;
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; i++)
        fin >> pct[i].x >> pct[i].y;
    int pos = 1;
    for (int i = 1; i <= N; i++)
        if (pct[i] < pct[pos])
            pos = i;
    swap(pct[1], pct[pos]);
    sort(pct + 2, pct + N + 1, cmp);
    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(pct[st[top - 1]], pct[st[top]], pct[i]) <= 0)
            --top;
        st[++top] = i;
    }
    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;
}