Cod sursa(job #2981799)

Utilizator PescaPescariu Matei Alexandru Pesca Data 18 februarie 2023 19:01:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
int const N=15e4;
#define float double
#define coord pair<float,float>
coord cord[N];
int n;
double area(coord A,coord B,coord C)
{
    double rez=0;
    rez+=A.first*B.second;
    rez+=B.first*C.second;
    rez+=C.first*A.second;
    rez-=B.second*C.first;
    rez-=C.second*A.first;
    rez-=A.second*B.first;
    return rez;

}
int Mystack[N];
int rez[N],reznr;
void solveST()
{
    int poz=0;
    for(int i=0;i<n;i++)
    {
        while(poz>1 && area(cord[Mystack[poz-2]],cord[Mystack[poz-1]],cord[i])>0)
            poz--;
        Mystack[poz++]=i;
    }
    reznr=poz;
    for(int i=0;i<poz;i++)
        rez[i]=Mystack[i];
}
void solveDR()
{
    int poz=0;
    for(int i=0;i<n;i++)
    {
        while(poz>1 && area(cord[Mystack[poz-2]],cord[Mystack[poz-1]],cord[i])<0)
            poz--;
        Mystack[poz++]=i;
    }
    for(int i=1;i<poz-1;i++)
        rez[reznr+i-1]=Mystack[poz-i-1];
        reznr+=poz-2;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        double x,y;
        cin>>x>>y;
        cord[i]={x,y};
    }
    sort(cord,cord+n);
    solveST();
    solveDR();
    cout<<reznr<<'\n';
    for(int i=0;i<reznr;i++)
        cout<<cord[rez[i]].first<<' '<<cord[rez[i]].second<<'\n';
}