Cod sursa(job #2572614)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 5 martie 2020 13:34:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 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 (A.y - B.y) * (B.x - C.x) < (A.x - B.x) * (B.y - C.y);
}

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

void Do()
{
    int i,j;
    int xmin = INF, ymin = INF, idx;
    idx = 1;
    xmin = a[1].x;
    ymin = a[1].y;
    punct A,B;
    vector<int> S;
    for(i = 1; i<=n; ++i)
    {
        if(a[i].y < ymin)
        {
            xmin = a[i].x ;
            ymin = a[i].y ;
            idx = i;
        }
        else if(a[i].y == ymin && a[i].x < xmin)
             {
                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(S.size()>=2 && !orient(a[S[S.size()-2]], a[S[S.size()-1]], 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;
}