Cod sursa(job #2535682)

Utilizator iarinatudorTudor Iarina Maria iarinatudor Data 1 februarie 2020 10:30:09
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 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;
vector <punct> V;
vector <punct> B;
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()

{
    V.push_back(v[0]);
    V.push_back(v[1]);
    int k=2;
    for(int i=2; i<n; i++)
    {
        while(k > 1 && det(V[k-2],V[k-1],v[i])==-1)
        {
            V.pop_back();
            k--;

        }
        V.push_back(v[i]);
        k++;
    }
    B.push_back(v[n-1]);
    B.push_back(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)
        {
            B.pop_back();
            aux--;
        }
        B.push_back(v[i]);
        aux++;
    }
    fout<<k+aux-2<<"\n";
    for(int i=0; i<k; i++)
    {
        fout<<setprecision(6)<<fixed;
        fout<<V[i].x<<" "<<V[i].y<<"\n";
    }
    for(int i=1; i<aux-1; i++)
    {
        fout<<setprecision(6)<<fixed;
        fout<<B[i].x<<" "<<B[i].y<<"\n";
    }
}
int main()
{
    citire();
    infasuratoare();
    return 0;
}