Cod sursa(job #3205872)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 20 februarie 2024 19:45:18
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb

#include <fstream>
#include <vector>
#include <algorithm>
#include <deque>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,poz;
vector<pair<double,double>> A;
double cross_product(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);
}
bool cmp (pair<double,double> a, pair<double,double> b)
{
    return cross_product(A[0],a,b)<0;
}
void convex_hull()
{
    deque<int> S;
    S.push_back(0);
    S.push_back(1);
    for(int i=2;i<n;i++)
    {
        while(S.size()>=2 && cross_product(A[S[S.size()-2]],A[S[S.size()-1]],A[i])>0)
           S.pop_back();
        S.push_back(i);
    }
    cout<<S.size()<<'\n';
    cout<<setprecision(9)<<fixed;
    for(int i=S.size()-1;i>=0;i--)
        cout<<A[S[i]].first<<" "<<A[S[i]].second<<'\n';
}
int main()
{
    cin>>n;
    A.resize(n);
    for(int i=0;i<n;i++)
      cin>>A[i].first>>A[i].second;
    for(int i=0;i<n;i++)
       if(A[i]<A[poz])
          poz=i;
    swap(A[0],A[poz]);
    sort(A.begin()+1,A.end(),cmp);
    convex_hull();
    return 0;
}