Cod sursa(job #3001201)

Utilizator rARES_4Popa Rares rARES_4 Data 13 martie 2023 12:45:45
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include<iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct punct{
float x,y;
}puncte[120001];
punct pct_minim;
int indice_min;
vector<punct>st;

float det(punct a,punct b,punct c)
{
    float det = a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-b.x*a.y-c.y*a.x;
    return det;
}
bool cmp(punct a,punct b)
{
    if(det(pct_minim,a,b)>0)
        return true;
    return false;
}
bool sens_poz(punct a,punct b,punct c)
{
    if(det(a,b,c)<=0)
        return 0;
    return 1;
}
void gasire_punct()
{
    pct_minim.x = 2000000000.00;
    pct_minim.y=2000000000.00;
    for(int i = 1;i<=n;i++)
    {
        if(pct_minim.x>puncte[i].x)
        {
            pct_minim.x = puncte[i].x;
            pct_minim.y = puncte[i].y;
            indice_min = i;
        }
        else
                if(pct_minim.x==puncte[i].x && pct_minim.y>puncte[i].y)
                {
                    pct_minim.y = puncte[i].y;
                    indice_min = i;
                }
    }
}
int main()
{
    f >> n;
    for(int i = 1;i<=n;i++)
    {
        f >> puncte[i].x>> puncte[i].y;
    }
    gasire_punct();
    swap(puncte[1],puncte[indice_min]);
    sort(puncte+2,puncte+1+n,cmp);
    st.push_back(puncte[1]);
    st.push_back(puncte[2]);
    for(int i =3;i<=n;i++)
    {
        punct pct = puncte[i];
        punct pct1 = st.back();
        punct pct2 = st[st.size()-2];

        while(!sens_poz(pct2,pct1,pct))
        {
            st.pop_back();
            pct1 = st.back();
            pct2 = st[st.size()-2];
        }
        st.push_back(pct);
    }
    g << st.size()<<'\n';
    int l = st.size();
    for(int i =0;i<l;i++)
        g << fixed<< setprecision(6)<< st[i].x << " "<< setprecision(6)<< st[i].y<< "\n";

}