Cod sursa(job #2535749)

Utilizator ana_maria_zotaZota Ana Maria ana_maria_zota Data 1 februarie 2020 11:07:32
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;

struct punct{
    double x,y;
    bool operator <(const punct& a) const
    {
        if(a.x==x)
            return (a.y>y);
        return (a.x>x);
    }
};

vector<punct>v;
vector<punct>V;
vector<punct>b;

int determinant(punct a,punct b,punct c)
{
    double u=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
    if(u<=0)
        return 0;
    else
        return 1;
    
}

void solve()
{
    V.push_back(v[0]);
    V.push_back(v[1]);
    int k=2;
    
    for(int i=2;i<n;i++)
    {
         
       while( k>1 &&determinant(V[k-2], V[k-1], v[i])==0 )
        {
            k--;
            V.pop_back();
        }
        
        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 && determinant(b[aux-2], b[aux-1], v[i])==0)
        {
            aux--;
            b.pop_back();
        }
        
        b.push_back(v[i]);
        aux++;
    }
    
    V.pop_back();
    b.pop_back();
    
  int s=k+aux-2;
    
    fout<<s<<"\n";
    fout<<setprecision(6)<<fixed;

    for(int i=0;i<k-1;i++)
    {
        fout<<V[i].x<<" "<<V[i].y;
        fout<<"\n";
    }
    for(int i=0;i<aux-1;i++)
    {
        fout<<b[i].x<<" "<<b[i].y;
        fout<<"\n";
    }
}
int main( ) {
    
    fin>>n;
    v.resize(n);
    
    for(int i=0;i<n;i++)
    {
        fin>>v[i].x>>v[i].y;
    }
    
    sort( v.begin(), v.end());
    /*for(int i=0;i<n;i++)
       {
           fout<<v[i].x<< " " << v[i].y;
           fout<<"\n";
       }*/
   solve();
    return 0;
}