Cod sursa(job #2327856)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 25 ianuarie 2019 01:57:31
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct
{
    double x, y;
};
punct p[120002], s[120002];
double pi(punct A, punct B, punct C)
{
    return (A.x-C.x)*(B.y-C.y)-(B.x-C.x)*(A.y-C.y);
}
int criteriu (punct A, punct B)
{
    return pi(A, B, p[0])>0;
}
int n, i, sf, poz;
double miny, minx;
int main()
{
    fin >> n;
    n--;
    for(i=0;i<=n;i++)
        {
            fin >> p[i].x >> p[i].y;
            if(p[i].y<miny)
            {
                miny=p[i].y;
                minx=p[i].y;
                poz=i;
            }
            else if(p[i].y==miny&&p[i].x<minx)
            {
                minx=p[i].x;
                poz=i;
            }
        }
    swap(p[0], p[poz]);
    sort(p+1, p+n+1, criteriu);
    s[0]=p[0];
    s[1]=p[1];
    s[2]=p[2];
    sf=2;
    for(i=3;i<=n;i++)
    {
        while(pi(p[i], s[sf], s[sf-1])>0)
            sf--;
        sf++;
        s[sf]=p[i];
    }
    fout << sf+1 << '\n';
    for(i=0;i<=sf;i++)
        fout << setprecision(12) << fixed << p[i].x << ' ' << p[i].y << '\n';
    return 0;
}