Cod sursa(job #2572565)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 5 martie 2020 13:22:01
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;

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

const int NMAX = 120009;

const int INF = 1<<30;

struct punct{
    double x,y;
}a[NMAX];

int n;

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

bool orient(punct A, punct B, punct C)
{
    return (B.y - A.y) * (C.x - B.x) < (B.x - A.x) * (C.y - B.y);
}

bool comp(punct A, punct B)
{
    return orient(a[1], A, B);
}

void Do()
{
    int i,j;
    int xmin = INF, ymin = INF, idx;
    punct A,B;
    vector<int> S;
    for(i = 1; i<=n; ++i)
    {
        if(a[i].x < xmin)
        {
            xmin = a[i].x ;
            ymin = a[i].y ;
            idx = i;
        }
        else if(a[i].x == xmin && a[i].y < ymin)
             {
                xmin = a[i].x ;
                ymin = a[i].y ;
                idx = i;
             }
    }
    swap(a[1], a[idx]);
    sort(a+2, a+n+1, comp);
    S.push_back(1);
    S.push_back(2);
    for(i = 3; i<=n; ++i)
    {
        while(!orient(a[S.size()-2], a[S.back()], a[i] ))
            S.pop_back();
        S.push_back(i);
    }
    fout<<S.size()<<"\n";
    for(i = 0; i<S.size(); ++i)
        fout<<fixed<<setprecision(6)<<a[S[i]].x<<" "<<a[S[i]].y<<"\n";

}

int main()
{
    Read();
    Do();
    return 0;
}