Cod sursa(job #2535730)

Utilizator iarinatudorTudor Iarina Maria iarinatudor Data 1 februarie 2020 11:00:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
    double x,y;
    bool operator <(const punct& other) const
    {
        if(x == other.x)
            return (y < other.y);

        return x < other.x;
    }
};
int n;
vector <punct> v;
punct a[120005],b[120005];
void citire()
{
    fin>>n;
    v.resize(n);
    for(int i=0; i<n; i++)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v.begin(),v.end());
}

int det(punct a,punct b,punct c)
{
    return ((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)>0);
}
void infasuratoare()
{
    a[0]=v[0];
    a[1]=v[1];
    int k=2;
    for(int i=2; i<n; i++)
    {
        while(k > 1 && det(a[k-2],a[k-1],v[i])==0)
            k--;
        a[k++]=v[i];
    }

   b[0]=v[n-1];
   b[1]=v[n-2];
    int aux=2;
    for(int i=n-3; i>=0; i--)
    {
        while(aux>1&&det(b[aux-2],b[aux-1],v[i])==0)
            aux--;
       b[aux++]=v[i];
    }

    fout<<k+aux-2<<"\n";

    for(int i=0; i<k-1; i++)
    {
        fout<<setprecision(6)<<fixed;
        fout<<a[i].x<<" "<<a[i].y<<"\n";
    }
    for(int i=0; i<aux-1; i++)
    {
        fout<<setprecision(6)<<fixed;
        fout<<b[i].x<<" "<<b[i].y<<"\n";
    }
}
int main()
{
    citire();
    infasuratoare();
    return 0;
}