Cod sursa(job #2573083)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 5 martie 2020 15:44:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
#define ld long double
#define Nmax 120005
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
    ld x, y;
};
punct p[Nmax];
int n, nr, s[Nmax], r;
ld produs(punct A, punct B, punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
ld distanta(punct A, punct B)
{
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}
bool criteriu(punct A, punct B)
{
    if(produs(p[1], A, B)==0)
        return distanta(p[1], A)<distanta(p[1], B);
    return produs(p[1], A, B)>0;
}
int gaseste()
{
    ld minx=p[1].x, miny=p[1].y;
    int r;
    for(int i=2;i<=n;i++)
    {
        if(minx>p[i].x)
        {
            minx=p[i].x;
            miny=p[i].y;
            r=i;
        }
        else if(minx==p[i].x && miny>p[i].y)
        {
            miny=p[i].y;
            r=i;
        }
    }
    return r;
}
int main()
{
    fin >> n;
    fin >> p[1].x >> p[1].y;
    for(int i=2;i<=n;i++)
        fin >> p[i].x >> p[i].y;
    r=gaseste();
    swap(p[1], p[r]);
    sort(p+2, p+n+1, criteriu);
    nr=1;
    s[1]=1;
    for(int i=2;i<=n;i++)
    {
        while(nr>1 && produs(p[s[nr-1]], p[s[nr]], p[i])<0)
            nr--;
        nr++;
        s[nr]=i;
    }
    fout << nr << '\n';
    for(int i=1;i<=nr;i++)
        fout << setprecision(12) << fixed << p[s[i]].x << ' ' << p[s[i]].y << '\n';
    return 0;
}