Cod sursa(job #1300417)

Utilizator somuBanil Ardej somu Data 24 decembrie 2014 13:56:11
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define nmax 120005
using namespace std;

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

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

int n, sSize;
int st[nmax];
bool VIZ[nmax];

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

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)-(B.x-O.x)*(A.y-O.y);
}

void solve() {
    int i;
    sort(P+1, P+n+1, cmp);
    st[1] = 1;
    st[2] = 2;
    VIZ[st[1]] = VIZ[st[2]] = true;
    sSize = 2;
    for (i = 3; i <= n; i++) {
        while (sSize > 1 && det(P[st[sSize-1]], P[st[sSize]], P[i]) < 0.000000000001) {
            VIZ[st[sSize]] = false;
            sSize--;
        }
        sSize++;
        st[sSize] = i;
        VIZ[st[sSize]] = true;
    }
    for (i = n-1; i > 0; i--) {
        if (VIZ[i])
            continue;
        if (det(P[st[sSize-1]], P[st[sSize]], P[i]) < 0)
            sSize--;
        sSize++;
        st[sSize] = i;
    }
}

void writeData() {
    int i;
    fout << sSize << "\n";
    fout << fixed;
    for (i = 1; i <= sSize; i++)
        fout << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << "\n";
}

int main() {
    readData();
    solve();
    writeData();
    fin.close();
    fout.close();
    return 0;
}