Cod sursa(job #2834869)

Utilizator rARES_4Popa Rares rARES_4 Data 17 ianuarie 2022 19:49:08
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 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 pct{
    double x,y;
}puncte[120001],punt_jos_stanga;
vector<pct>infasuratoare;

double determinant(pct a,pct b,pct c)
{
    return ((a.x*b.y) + (a.y*c.x) + (b.x*c.y) - (b.y*c.x) - (c.y*a.x) - (a.y*b.x));
}

bool comp(pct a,pct b)
{
    if(determinant(punt_jos_stanga,a,b)>0)
        return true;
    return false;
}

void init()
{
    sort(puncte+1,puncte+1+n,comp);
}

bool sens_trigonometric(pct a,pct b,pct c)
{
        if(determinant(a,b,c)>0)
            return true;
        return false;
}

void alg()
{
    infasuratoare.push_back(punt_jos_stanga);
    infasuratoare.push_back(puncte[2]);
    for(int i = 3;i<=n;i++)
    {
        while(!sens_trigonometric(infasuratoare[infasuratoare.size()-2],infasuratoare[infasuratoare.size()-1],puncte[i]))
            infasuratoare.pop_back();
        infasuratoare.push_back(puncte[i]);
    }
}

void afisare()
{
    g << infasuratoare.size()<< endl;
    for(int i = 0;i<infasuratoare.size();i++)
        g << fixed<<setprecision(6)<< infasuratoare[i].x << " "<< infasuratoare[i].y<< '\n';
}

void citire()
{
    punt_jos_stanga.x = 2000000000;
    punt_jos_stanga.y = 2000000000;
    f >> n;
    for(int i= 1;i<=n;i++)
    {
        f >> puncte[i].x >> puncte[i].y;


        //gasim cel mai de jos punct, iar daca sunt mai multe la fel de jos cel mai din stanga
        // suntem siguri ca acel punct apartine infasuratorii, asa ca de acolo incepem algoritmul
        if(puncte[i].y<punt_jos_stanga.y)
        {
            punt_jos_stanga.x = puncte[i].x;
            punt_jos_stanga.y = puncte[i].y;
        }
        else
            if(puncte[i].y==punt_jos_stanga.y && puncte[i].x<punt_jos_stanga.x)
                punt_jos_stanga.x = puncte[i].x;
    }
}
int main()
{
    citire();
    init();
    alg();
    afisare();
}