Cod sursa(job #1550433)

Utilizator fromzerotoheroFROM ZERO fromzerotohero Data 13 decembrie 2015 18:19:43
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>

#define nmax 120001
#define inf (1<<30)
#define E 0.000000000001

using namespace std;

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

int n, s, stSize;
int st[nmax];
bool viz[nmax];
double swX, swY, seX, seY, neX, neY, nwX, nwY;

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

void init()
{
    swX = swY = seY = nwX = inf;
    seX = neX = neY = nwY = -inf;
}

void process(int x, int y)
{
    if (x < swX || y < swY)
        swX = x, swY = y;
    
    if (x > seX || y < seY)
        seX = x, seY = y; // South East X - dirty minded
    
    if (x > neX || y > neY)
        neX = x, neY = y;
    
    if (x < nwX || y > nwY)
        nwX = x, nwY = y;
    
}

bool checkIfInside(int x, int y)
{
    if ((x > swX && x > nwX && x < seX && x < neX) && (y > swY && y < nwY && y > seY && y < neY))
        return true;
    return false;
    
}

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");
    
    init();
    
    fi >> n;
    for (int i = 1; i <= n; i++)
        fi >> AUX[i].x >> AUX[i].y,
        process(AUX[i].x, AUX[i].y);
    
    for (int i = 1; i <= n; i++)
        if (!checkIfInside(AUX[i].x, AUX[i].y))
        {
            s++;
            P[s].x = AUX[i].x, P[s].y = AUX[i].y;
            
        }
    
    sort(P+1, P+s+1, cmp);
    
    st[1] = 1;
    st[2] = 2;
    viz[1] = viz[2] = true;
    
    stSize = 2;
    
    for (int i = 3; i <= n; i++)
    {
        while (stSize > 1 && det(P[st[stSize-1]], P[st[stSize]], P[i]) > E)
            viz[st[stSize--]] = false;
    
        st[++stSize] = i;
        viz[i] = true;
        
    }
    
    for (int i = n; i > 0; i--)
    {
        if (viz[i])
            continue;
        
        while (stSize > 1 && det(P[st[stSize-1]], P[st[stSize]], P[i]) > E)
            st[stSize--] = false;
        
        st[++stSize] = i;
        
    }
    
    fo << stSize << "\n";
    fo << fixed;
    fo << setprecision(6) << P[st[1]].x << " " << P[st[1]].y << "\n";
    for (int i = stSize; i > 1; i--)
        fo << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << "\n";
    
    fi.close();
    fo.close();
    
    return 0;
    
}