Cod sursa(job #1471568)

Utilizator EpictetStamatin Cristian Epictet Data 14 august 2015 14:07:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

#define x first
#define y second

using namespace std;

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

int n, pos;
pair < double, double > V[120010];
int S[120010], top;

double Produs(pair < double, double > a, pair < double, double > b, pair < double, double > c)
{
    return ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y));
}

bool cmp(pair < double, double > a, pair < double, double > b)
{
    return (Produs(V[1], a, b) < 0);
}

int main()
{
    fin >> n;
    pos = 1;
    for (int i = 1; i <= n; i++)
    {
        fin >> V[i].x >> V[i].y;
        if (V[i] < V[pos])
        {
            pos = i;
        }
    }
    swap(V[1], V[pos]);
    sort(V + 2, V + 1 + n, cmp);
    S[++top] = 1;
    for (int i = 2; i <= n; i++)
    {
        while (top > 1 && Produs(V[S[top - 1]], V[S[top]], V[i]) > 0)
        {
            top--;
        }
        S[++top] = i;
    }

    fout << top << '\n';
    while (top)
    {
        fout << fixed << setprecision(6) << V[S[top]].x << ' ' << V[S[top]].y << '\n';
        top--;
    }

    fout.close();
    return 0;
}