Cod sursa(job #3212210)

Utilizator CobzaruAntonioCobzaru Paul-Antonio CobzaruAntonio Data 11 martie 2024 12:38:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
int n,poz;
long double xmin,ymin;
struct punct
{
    long double x,y;
};
punct v[120005];
punct q[120005];
punct p0;
long double dist(punct a,punct b)
{
    long double rasp = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
    return rasp;
}
long double orientare(punct a,punct b,punct c)
{
    long double v = (b.y-a.y)*(c.x-a.x) - (c.y-a.y)*(b.x-a.x);
    if(v==0)
        return 0;
    if(v>0)
        return 1;
    if(v<0)
        return 2;
}
bool fcmp(punct a,punct b)
{
    int o = orientare(p0,a,b);
    if(o==0)
    {
        if(dist(p0,a)>=dist(p0,b))
            return false;
        return true;
    }
    else
    {
        if(o==2)
            return true;
        return false;
    }
}
int main()
{
    int n;
    cin >> n;
    xmin = 2e9;
    ymin = 2e9;
    for(int i=1;i<=n;i++)
    {
        cin >> v[i].x >> v[i].y;
        if(v[i].y<ymin)
        {
            ymin = v[i].y;
            xmin = v[i].x;
            poz = i;
        }
        else if (v[i].y==ymin && v[i].x<xmin)
        {
            xmin = v[i].x;
            poz = i;
        }
    }
    swap(v[1],v[poz]);
    p0 = v[1];
    sort(v+2,v+n+1,fcmp);
    int vf = 2;
    q[1] = v[1];
    q[2] = v[2];
    for(int i=3;i<=n;i++)
    {
        while(vf>1 && orientare(q[vf-1],q[vf],v[i])!=2)
            vf--;
        q[++vf] = v[i];
    }
    cout << vf << '\n';
    for(int i=1;i<=vf;i++)
        cout << fixed << setprecision(15) << q[i].x << ' ' << q[i].y << '\n';
    return 0;
}