Cod sursa(job #2527130)

Utilizator MihaiB729Bucur Mihai MihaiB729 Data 19 ianuarie 2020 17:51:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 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()
{
    int poz=0;
    for(int i=1;i<v.size();i++)
        if(v[poz]>v[i])
        poz=i;
    swap(v[0],v[poz]);
    sort(v.begin()+1,v.end(),comp);
}
void rezconv()
{
    sortare();
    //fout<<v[0].first<<" "<<v[0].second<<endl;
    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;
}