Cod sursa(job #1566387)

Utilizator fromzerotoheroFROM ZERO fromzerotohero Data 12 ianuarie 2016 00:29:10
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstdlib>

#define nmax 120001

using namespace std;

struct point {
    
    double x, y;

} P[nmax];

int n;
int st[nmax];
int stackSize;

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 c)
{
    return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
}

int main()
{

    ifstream fi("infasuratoare.in");
    ofstream fo("infasuratoare.out");
    
    /*
     
     8
     2.0 0.0
     0.0 2.0
     1.0 3.0
     0.0 4.0
     3.0 3.0
     2.0 6.0
     4.0 2.0
     4.0 4.0
     
     */
    
    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;
    stackSize = 2;
    
    viz[st[1]] = viz[st[2]] = true;
    
    for (int i = 3; i <= n; i++)
    {
        
        while (stackSize > 1 && det(P[ st[stackSize-1] ], P[ st[stackSize] ], P[i]) < 0)
            viz[ st[stackSize--] ] = false;
        
        st[++stackSize] = i;
        viz[i] = true;
        
    }
    
    for (int i = n; i > 1; i--)
    {
        
        if (viz[i])
            continue;
        
        while (stackSize > 1 && det(P[ st[stackSize-1] ], P[ st[stackSize] ], P[i]) < 0)
            stackSize--;
        
        st[++stackSize] = i;
        
    }
    
    fo << stackSize << "\n";
    fo << fixed;
    for (int i = 1; i <= stackSize; i++)
        fo << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << "\n";
        
    
    fi.close();
    fo.close();
    
    return 0;
}