Cod sursa(job #2527135)

Utilizator MihaiB729Bucur Mihai MihaiB729 Data 19 ianuarie 2020 18:00:36
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x,y;
vector <pair <double,double> > v;
vector <pair <double,double> > s;
double prod(pair <double,double> A,pair <double,double> B,pair <double,double> C)
{
    return (B.first-A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first);
}
int comp(pair <double,double> A,pair <double,double> B)
{
    return prod(v[0],A,B)<0;
}
void sortare()
{
    sort(v.begin(),v.end());
    sort(v.begin()+1,v.end(),comp);
}
void rezconv()
{
    sortare();
    s.push_back(v[0]);
    s.push_back(v[1]);
    for(int i=2;i<v.size();i++)
    {
        while(s.size()>=1 && prod(s[s.size()-2],s[s.size()-1],v[i])>0)
            s.pop_back();
        s.push_back(v[i]);
    }
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>x>>y;
        v.push_back(make_pair(x,y));
    }
    rezconv();
    fout<<s.size()<<'\n';
    fout<<fixed;
    for(int i=s.size()-1;i>=0;i--)
        fout<<setprecision(9)<<s[i].first<<" "<<s[i].second<<'\n';
    return 0;
}