Cod sursa(job #1923082)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 10 martie 2017 20:39:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
Raporteaza aceasta sursa 
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

typedef pair <double, double> Point;
const int MAXN = 120010;
const int EPS = 1e-12;

int n;
Point v[MAXN];
bool vis[MAXN];
int st[MAXN], head;

void read()
{
    fin >> n;
    for(int i=1; i<=n; ++i)
        fin >> v[i].x >> v[i].y;
}

double cross_product(Point O, Point A, Point B){
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y); /// determinantul (Aria)
}

void convex_hull()
{
    /// sortam dupa x
    sort(v+1, v+n+1);
    /// este stiva mea de puncte din infasuratoare
    st[1] = 1; st[2] = 2; head = 2;
    ///introducem primele 2 elemente in infasuratoare si setam numarul de elemente din stiva
    vis[2] = 1;
    ///marcam 2 ca fiind vizitat

    for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p))) ///i este indicele nodului la care ma aflu, p este pasul, pozitiv sau negatv
    {
        if(vis[i]) continue;
        /// daca a fost vizitat nu l vizitam
        while(head >= 2 && cross_product(v[st[head-1]], v[st[head]], v[i]) <= EPS)
            ///cat timp directia este schimbata
            vis[st[head--]] = 0;
        st[++head] = i;
        vis[i] = 1;
    }

    ///scriem solutie
    fout<<head - 1<<'\n';
    fout<<setprecision(6)<<fixed;
    for(int i=1; i < head; ++i)
        fout<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
}

int main()
{
    read();
    convex_hull();
    return 0;
}