Cod sursa(job #3300596)

Utilizator KapetaneAvram Armand-Florin Kapetane Data 17 iunie 2025 18:04:50
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Punct 
{
    long double x,y;
};

Punct pivot;

long double distanta(Punct a,Punct b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

int orientare(Punct p,Punct q,Punct r)
{
    long double val = (q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);
    if(abs(val)<1e-12) return 0;
    return (val>0) ? 1 : 2;
}

bool compara(Punct a, Punct b)
{
    int o=orientare(pivot, a, b);
    if(o==0) return distanta(pivot,a)<distanta(pivot,b);
    return o==1;
}

int main() 
{   
    int n;
    fin>>n;
    Punct puncte[120001];
    
    int minim=0;
    for(int i=0;i<n;i++)
    {
        fin>>puncte[i].x>>puncte[i].y;
        if(puncte[i].y<puncte[minim].y || (puncte[i].y==puncte[minim].y && puncte[i].x<puncte[minim].x)) 
        {
            minim = i;
        }
    }
    
    swap(puncte[0],puncte[minim]);
    pivot=puncte[0];
    sort(puncte+1,puncte+n,compara);
    
    Punct infasuratoare[120001];
    int dimensiune=0;
    infasuratoare[dimensiune++]=puncte[0];
    infasuratoare[dimensiune++]=puncte[1];

    for(int i=2;i<n;i++)
     {
        while(dimensiune>=2 && orientare(infasuratoare[dimensiune-2],infasuratoare[dimensiune-1], puncte[i])!=1)
        {
            dimensiune--;
        }
        infasuratoare[dimensiune++]=puncte[i];
    }
    
    fout<<dimensiune<<endl;
    fout<<fixed<<setprecision(6);
    for(int i=0;i<dimensiune;i++)
    {
        fout<<infasuratoare[i].x<<" "<<infasuratoare[i].y<<endl;
    }
    fin.close();
    fout.close();
    return 0;
}