Cod sursa(job #2280191)

Utilizator opariucbiancaOpariuc Bianca Gabriela opariucbianca Data 10 noiembrie 2018 12:38:16
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include<iomanip>
#include <algorithm>

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

int n;
struct punct
{
    double x,y;
}p[120005],primul,s[120005];

inline double cp(punct A, punct B, punct C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

 int criteriu(punct p1, punct p2) {
    return cp(p[1], p1, p2) < 0;
}

int main()
{
    int vf,poz;
    fin>>n;
    fin>>p[1].x>>p[1].y;
    poz=1;
    for(int i=2;i<=n;i++)
    {
        fin>>p[i].x>>p[i].y;
        if(p[i].x<p[poz].x)
        {
            poz=i;
        }
       else
       {
           if(p[i].x==p[poz].x && p[i].y<p[poz].y)
           {
               poz=i;
           }
       }
    }
     swap(p[1], p[poz]);
     sort(p + 2, p + n + 1, criteriu);
    s[1]=p[1];
    s[2]=p[2];
    vf=2;
     for(int i=3;i<=n;i++)
     {
             while(vf>=2 && cp(s[vf-1],s[vf],p[i])>0)
             {
                 --vf;
             }
             s[++vf]=p[i];
     }
     fout << fixed;
     fout<<vf<<'\n';
     for (int i = vf; i >= 1; --i)
        fout << setprecision(5) << s[i].x << " " << s[i].y << "\n";
    return 0;
}