Cod sursa(job #2188645)

Utilizator Chirita_MateiChirita Matei Chirita_Matei Data 27 martie 2018 12:15:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

#define ld long double

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

struct Point{
    ld x;
    ld y;
};

Point p[120010];
Point st[120010];
Point mini;
int n;
int k;

ld area(Point a, Point b, Point c){
    return (ld)1/2 * (a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x);
}

bool comp(Point a, Point b){
    if(a.x == mini.x && a.y == mini.y) return 0;
    if(b.x == mini.x && b.y == mini.y) return 1;

    if(area(mini, a, b) > 0) return 1;
    return 0;
}

int main()
{
    fin >> n;

    mini.x = 1000000010;
    mini.y = 1000000010;

    for(int i = 0; i < n; i++){
        fin >> p[i].x >> p[i].y;
        if(p[i].x < mini.x)         mini.x = p[i].x, mini.y = p[i].y;
        else if(p[i].x == mini.x && p[i].y < mini.y) mini.y = p[i].y;
    }

    sort(p, p + n, comp);

    st[++k] = mini;
    st[++k] = p[0];

    for(int i = 1; i < n; i++){
        if(area(st[k - 1], st[k], p[i]) > 0) st[++k] = p[i];
        else{
            while(area(st[k - 1], st[k], p[i]) < 0 && k > 1) k--;
            st[++k] = p[i];
        }
    }

    fout << k - 1 << '\n';
    for(int i = 1; i <= k - 1; i++){
        fout << setprecision(12) << fixed << st[i].x << ' ' << st[i].y << '\n';
    }

    return 0;
}