Cod sursa(job #2543791)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 11 februarie 2020 15:29:51
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int Nmax = 120000, inf = 0x3f3f3f3f;

struct Point{
    double x, y;
    bool operator < (const Point &other){
        if (x == other.x)
            return y < other.y;
        return x < other.x;
    }
};

Point v[Nmax + 5], st[Nmax + 5];
Point p0;
int n, nr;

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

double Determinant(Point a, Point b, Point c){
    double s1 = 0, s2 = 0;
    s1 = b.x * c.y + a.x * b.y + c.x * a.y;
    s2 = b.x * a.y + c.x * b.y + c.y * a.x;
    return s1 - s2;
}

int Compare(Point a, Point b){
    return Determinant(p0, a, b) > 0;
}

void Solve(){
    p0.x = p0.y = inf;
    int pos = 0;
    for (int i = 1; i <= n; i++)
        if (v[i] < p0){
            p0 = v[i];
            pos = i;
        }
    swap(v[pos], v[1]);
    sort(v + 1, v + n + 1, Compare);
    st[1] = v[1];
    st[2] = v[2];
    nr = 2;
    for (int i = 3; i <= n; i++){
        while (nr >= 2 && Determinant(st[nr - 1], st[nr], v[i]) < 0)
            nr--;
        st[++nr] = v[i];
    }
}

void Print(){
    fout << nr << '\n';
    for (int i = 1; i <= nr; i++){
        fout << fixed << setprecision(6) << st[i].x << ' ';
        fout << fixed << setprecision(6) << st[i].y << '\n';
    }
}

int main(){
    Read();
    Solve();
    Print();
    return 0;
}