Cod sursa(job #2543986)

Utilizator betybety bety bety Data 11 februarie 2020 17:58:53
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int lim=120000+5;
struct point
{
    float x,y;
}v[lim];
vector<int> sol;
int main()
{
    float mx=1000000001.0,my;
    int n,ind;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i].x>>v[i].y;
        if(v[i].x<mx)
        {
            ind=i;
            mx=v[i].x;
            my=v[i].y;
        }
        else if(v[i].x==mx and v[i].y<my)
        {
            ind=i;
            my=v[i].y;
        }
    }
    do
    {
        sol.push_back(ind);
        int r=1;
        if(ind==1)
            r=2;
        for(int i=r+1;i<=n;++i)
        if(i!=ind and (v[i].x-v[ind].x)*(v[r].y-v[ind].y)>(v[r].x-v[ind].x)*(v[i].y-v[ind].y))
            r=i;
        ind=r;
    }while(ind!=sol[0]);
    cout<<sol.size()<<'\n';
    for(int i=0;i<sol.size();++i)
        cout<<setprecision(6)<<fixed<<v[sol[i]].x<<' '<<v[sol[i]].y<<'\n';
    return 0;
}