Mai intai trebuie sa te autentifici.

Cod sursa(job #2380337)

Utilizator ianiIani Biro iani Data 14 martie 2019 20:03:36
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <iomanip>

#define MAXN 120005

using namespace std;

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

int n;

typedef pair<double,double> Point;

Point a[MAXN];
Point steve[MAXN];

void citire()
{
    fin>>n;
    for (int i=1;i<=n;i++)
    {
        double x,y;
        fin>>x>>y;
        a[i]=make_pair(x, y);
    }
}

double cross_product(Point a,Point b,Point c)
{
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
    //If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn" or counter-clockwise orientation, otherwise a "right turn" or clockwise orientation
}

int cmp(const Point& p1, const Point& p2) {
    return cross_product(a[1], p1, p2) < 0;
}

void sort_points() {
    int pos = 1;
    for (int i = 2; i <= n; ++i)
        if (a[i] < a[pos])
            pos = i;
    swap(a[1], a[pos]);
    sort(a + 2, a + n + 1, cmp);
}

void convex_hull()
{
    sort_points();
    
    steve[1]=a[1];
    steve[2]=a[2];
    int vf=2;
    
    for (int i=3;i<=n;i++)
    {
        while (vf>2&&cross_product(steve[vf-1], steve[vf], a[i])>0)
            vf--;
        steve[++vf]=a[i];
    }
    fout<<vf<<'\n';
    fout<<setprecision(6)<<fixed;
    for (int i=vf;i>=1;i--)
        fout<<steve[i].first<<' '<<steve[i].second<<'\n';
}

int main()
{
    citire();
    convex_hull();
    return 0;
}