Cod sursa(job #3344415)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 1 martie 2026 22:49:27
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define VMAX 200005
#define INF 1e10
#define int long long int
#define double long double
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct pct{

double i,j;
    pct (double i_=0,double j_=0): i(i_),j(j_) {};

};

vector<pct> numere;

vector<int> luate;

double arie(pct a, pct b, pct c)
{
    return a.i*b.j+b.i*c.j+c.i*a.j-a.i*c.j-b.i*a.j-c.i*b.j;
}

bool comp(pct a, pct b)
{
    return arie(numere[0],a,b)>0;
}


signed main()
{
    ios_base::sync_with_stdio(0);
    int n,m,i,j,k,t,nr,minim,maxim,suma,st,dr,mij;
    double p,q;

    fin>>n;
    for(i=0;i<n;i++)
    {
        fin>>p>>q;
        numere.push_back(pct(p,q));
        if(numere[i].i<numere[0].i || numere[i].i==numere[0].i && numere[i].j<numere[0].j)
        {
            swap(numere[0],numere[i]);
        }
    }

    sort(numere.begin()+1,numere.end(),comp);

    luate.push_back(0);

    for(i=1;i<numere.size();i++)
    {
        while(luate.size()>=2 && arie(numere[luate[luate.size()-2]],numere[luate[luate.size()-1]],numere[i])<0)
            luate.pop_back();
        luate.push_back(i);
    }


    fout<<luate.size()<<'\n';
    for(auto it:luate)
        fout<<fixed<<setprecision(7)<<numere[it].i<<' '<<numere[it].j<<'\n';












    return 0;
}