Cod sursa(job #2371442)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 6 martie 2019 17:39:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

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

int xs,ys,n;
int start;

struct point
{
    double x,y;
}a[123000],S[123000];

void Read()
{
    int i;
    double xmin=1000000003;
    double ymin= 1000000003;
    fin>>n;
    for(i=1; i<=n; ++i)
    {
        fin>>a[i].x>>a[i].y;
        if(ymin>a[i].y)
        {
          start=i;
          xmin=a[i].x;
          ymin=a[i].y;
        }
        else if(ymin==a[i].y && xmin>a[i].x)
             {
                start=i;
                xmin=a[i].x;
                ymin=a[i].y;
             }
    }
}

bool Orientare(point k, point l, point m)
{
    long double o1=1LL*(k.y-l.y)*(l.x-m.x);
    long double o2=1LL*(l.y-m.y)*(k.x-l.x);
    return (o1<=o2);
}

bool comp(point A, point B)
{
    return (Orientare(a[start],A,B));
}

void Do()
{
    int i,j;
    swap(a[1],a[start]);
    sort(a+2,a+n+1,comp);
    //cout<<Orientare(a[1],a[2],a[3]);

    vector<int> S;

    S.push_back(1);
    S.push_back(2);
    S.push_back(3);
    for(i=4; i<=n; ++i)
    {
        while(!Orientare(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;
}