Cod sursa(job #2201017)

Utilizator Chirita_MateiChirita Matei Chirita_Matei Data 3 mai 2018 10:10:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

#define ld long double

using namespace std;

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

struct Point{
    ld x;
    ld y;
};

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

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, pos = i;
        else if(p[i].x == mini.x && p[i].y < mini.y) mini.y = p[i].y, pos = i;
    }
    swap(p[0], p[pos]);
    sort(p + 1, p + n, comp);
    p[n] = mini;
    st[++k] = mini;
    st[++k] = p[1];

    for(int i = 2; 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';
    fout << setprecision(12) << fixed;
    for(int i = 1; i <= k - 1; i++){
        fout << st[i].x << ' ' << st[i].y << '\n';
    }

    return 0;
}