Cod sursa(job #1951372)

Utilizator Train1Train1 Train1 Data 3 aprilie 2017 16:22:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define maxN 120001
#define xMax 1000000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, aux;
struct punct {
    double x, y;
} v[maxN];
int st[maxN];
bool prod(punct O, punct A, punct B) {
    double p1 = (A.y - O.y)*(B.x - O.x);
    double p2 = (B.y - O.y)*(A.x - O.x);
    return p1 < p2;
}
bool comp(punct A, punct B) {
    return prod(v[1], A, B);
}
int main()
{
    fin>>n;
    punct P;
    P.x = xMax;
    P.y = xMax;
    for(int i = 1; i <= n; i++) {
        fin>>v[i].x>>v[i].y;
        if(v[i].x < P.x) {
            P.x = v[i].x;
            P.y = v[i].y;
            aux = i;
        } else if (v[i].x == P.x) {
            if(v[i].y < P.y) {
                P.y = v[i].y;
                aux = i;
            }
        }
    }
    P = v[aux];
    v[aux] = v[1];
    v[1] = P;
    sort(v + 2, v + n + 1, comp);
    int k = 2;
    st[1] = 1;
    st[2] = 2;
    for(int i = 3; i <= n; i++) {
        while(!prod(v[st[k - 1]], v[st[k]], v[i]) && k >= 2) {
            k--;
        }
        k++;
        st[k] = i;
    }
    fout<<fixed;
    fout<<k<<'\n';
    for(int i = 1; i <= k; i++) {
        fout<<setprecision(9)<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}