Cod sursa(job #2535696)

Utilizator iarinatudorTudor Iarina Maria iarinatudor Data 1 februarie 2020 10:41:36
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 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 <(punct a)
    {
        if(a.x==x)
            return (a.y>y);

        return (a.x>x);
    }
};
int n;
vector <punct> v;
punct a[120005],b[120005];
void citire()
{
    fin>>n;
    v.reserve(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)
{
    if((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)>0)
        return 1;
    else return -1;
}
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])==-1)
        {
            k--;
        }
        a[k]=v[i];
        k++;
    }

   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])==-1)
        {
            aux--;
        }
       b[aux]=v[i];
        aux++;
    }

    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;
}