Cod sursa(job #3159130)

Utilizator bexxRebeca N bexx Data 20 octombrie 2023 19:10:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

int n,k=2;
struct point{
    double x,y;
}v[120000],sol[120000];
enum orientare
{
    trigonometric,
    orar,
    coliniar,
};
void citire()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>v[i].x>>v[i].y;
    }
}
void afisare()
{
    cout<<k<<'\n';
    for(int i=0;i<k;i++)
        cout<<fixed<<setprecision(6)<<sol[i].x<<' '<<sol[i].y<<'\n';
}
bool cmp(point a,point b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
double det(point p1,point p2,point p3)
{
    return (p1.y-p2.y)*(p3.x-p2.x)-(p3.y-p2.y)*(p1.x-p2.x);
}
orientare calcul(point a,point b,point c)
{
    double d=det(a,b,c);
    if(d>0)
        return trigonometric;
    if(d==0)
        return coliniar;
    return orar;
}
void bkt()
{
    for(int x=2;x<n;x++)
    {
        while(calcul(sol[k-2],sol[k-1],v[x])==trigonometric)
        {
            k--;
        }
        sol[k++]=v[x];
    }
}
void bkt2()
{
    for(int x=n-2;x>=0;x--)
    {
        while(calcul(sol[k-2],sol[k-1],v[x])==trigonometric)
        {
            k--;
        }
        sol[k++]=v[x];
    }
}
int main()
{
    citire();
    sort(v,v+n,cmp);
    sol[0]=v[0];
    sol[1]=v[1];
    bkt();
    bkt2();
    k--;
    afisare();
    return 0;
}