Cod sursa(job #3359326)

Utilizator borduz-alexandru_ioanBorduz Alexandru Ioan borduz-alexandru_ioan Data 27 iunie 2026 00:43:18
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct
{
    double x,y;
};
bool compar_pct(punct a,punct b)
{
    if(abs(a.x-b.x)>1e-12)
        {
            return a.x<b.x;
        }   
    return a.y<b.y;
}
double produs_vect(punct o,punct a, punct b)
{
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int main (void)
{
    int n;
    f>>n;
    vector<punct> puncte(n);
    for(int i=0;i<n;++i)
    {
        f>>puncte[i].x>>puncte[i].y;
    }
    sort(puncte.begin(),puncte.end(),compar_pct);
    vector<punct> infasurare(2*n);
    int k=0;
    for(int i=0;i<n;i++)
    {
        while(k>=2 && produs_vect(infasurare[k-2],infasurare[k-1],puncte[i])<=1e-12)
        {
            k--;
        }
        infasurare[k++]=puncte[i];
    }
    int s=k+1;
    for(int i=n-2;i>=0;i--)
    {
        while(k>=s && produs_vect(infasurare[k-2],infasurare[k-1],puncte[i])<=1e-12)
        {
            k--;
        }
        infasurare[k++]=puncte[i];
    }
    infasurare.resize(k-1);
    g<<infasurare.size()<<'\n';
    g<<fixed<<setprecision(6);
    for(size_t i=0;i<infasurare.size();i++)
    {
        g<<infasurare[i].x<<" "<<infasurare[i].y<<'\n';
    }
    return 0;
}