Cod sursa(job #1256763)

Utilizator diana97Diana Ghinea diana97 Data 6 noiembrie 2014 20:34:20
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

struct Punct {
    double x, y;
};

const int NMAX = 120000 + 1;
int n, begin, end;
int stiva[NMAX];
bool pus[NMAX];
Punct punct[NMAX];

void citeste() {
    f >> n;
    for (int i = 1; i <= n; i++) f >> punct[i].x >> punct[i].y;
}

inline bool conditie(Punct a, Punct b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

inline bool semn(Punct a, Punct b, Punct c) {
    double x = a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
    return (x < 0);
}


void rezolva() {
    begin = 1; end = 2;
    stiva[1] = 1; pus[1] = true;
    stiva[2] = 2; pus[2] = true;
    int pas = 1;
    for (int i = 3; i > 0; i += pas) {
        if (i == n) pas *= (-1);
        if (!pus[i]) {
            while (end >= 2 && semn(punct[stiva[end - 1]], punct[stiva[end]], punct[i])) pus[stiva[end--]] = false;
            pus[i] = true;
            stiva[++end] = i;
        }
    }
    g << end << '\n';
    for (int i = begin; i <= end; i++) g << fixed << setprecision(6) << punct[stiva[i]].x << ' ' << punct[stiva[i]].y << '\n';
}

int main() {
    citeste();
    sort(punct + 1, punct + n + 1, conditie);
    rezolva();
    return 0;
}