Cod sursa(job #2853708)

Utilizator rARES_4Popa Rares rARES_4 Data 20 februarie 2022 15:39:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 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{
double x,y;
}puncte[120001],punct_jos_stanga;
vector<punct>rasp;
int indice= -1;
double determinant(punct a,punct b,punct c)
{
    return a.x*b.y + a.y*c.x + c.y*b.x - b.y*c.x - a.y*b.x - c.y*a.x;
}
bool cmp(punct a,punct b)
{
    if(determinant(punct_jos_stanga,a,b)>0)
        return true;
    return false;
}
void gasire_punct()
{
    punct_jos_stanga.x = 2000000000.00;
    punct_jos_stanga.y = 2000000000.00;
    for(int i = 1;i<=n;i++)
    {
        if(punct_jos_stanga.x>puncte[i].x)
        {
            punct_jos_stanga = puncte[i];
            indice = i;
        }
        else
            if(punct_jos_stanga.x==puncte[i].x && punct_jos_stanga.y>puncte[i].y)
        {
            punct_jos_stanga.y = puncte[i].y;
            indice = i;
        }

    }
}
bool sens_cesornic(punct a,punct b,punct c)
{
    if(determinant(a,b,c)<=0)
        return true;
    return false;
}
void alg()
{
    rasp.push_back(punct_jos_stanga);
    rasp.push_back(puncte[2]);

    for(int i = 3;i<=n;i++)
    {
        while(sens_cesornic(rasp[rasp.size()-2],rasp[rasp.size()-1],puncte[i]))
            rasp.pop_back();
        rasp.push_back(puncte[i]);
    }
}
void citire()
{
    f >> n;
    for(int i = 1;i<=n;i++)
    {
        f >> puncte[i].x>> puncte[i].y;
    }
    gasire_punct();
    swap(puncte[1],puncte[indice]);

    sort(puncte+2,puncte+1+n,cmp);
}
int main()
{
    citire();
    alg();
    g << rasp.size()<< "\n";
    for(int i = 0;i<rasp.size();i++)
    {
        g << fixed<< setprecision(6)<< rasp[i].x << " "<< setprecision(6)<< rasp[i].y<< "\n";
    }
}