Cod sursa(job #1408700)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 30 martie 2015 10:41:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define nmax 120005
#define E 0.000000000001

using namespace std;

struct point {
    double x, y;
} P[nmax];

int n, lenSt;
int st[nmax];
bool viz[nmax];

bool cmp(point a, point b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

double det(point a, point b, point o)
{
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}

int main()
{
    
    ifstream fi("infasuratoare.in");
    ofstream fo("infasuratoare.out");
    
    fi >> n;
    for (int i = 1; i <= n; i++)
        fi >> P[i].x >> P[i].y;
    
    sort(P+1, P+n+1, cmp);

    st[1] = 1, st[2] = 2;
    viz[st[1]] = viz[st[2]] = true;
    lenSt = 2;
    
    for (int i = 1; i <= n; i++)
    {
        while (lenSt > 1 && det(P[st[lenSt-1]], P[st[lenSt]], P[i]) < E)
            viz[st[lenSt--]] = false;
        st[++lenSt] = i;
        viz[st[lenSt]] = true;
    }
    
    for (int i = n; i > 0; i--)
    {
        if (viz[i])
            continue;
        while (lenSt > 1 && det(P[st[lenSt-1]], P[st[lenSt]], P[i]) < E)
            lenSt--;
        st[++lenSt] = i;
    }
    
    fo << lenSt-1 << "\n";
    fo << fixed;
    for (int i = 1; i < lenSt; i++)
        fo << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << "\n";
    
    fi.close();
    fo.close();
    
    return 0;
}