Cod sursa(job #3149929)

Utilizator NarcisMMic Narcis NarcisM Data 13 septembrie 2023 18:07:32
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoareconvexa.in");
ofstream fout("infasuratoareconvexa.out");
const int nm=120001;
struct coord{double x,y;};
stack <coord> stiva, af;
coord p[nm], /// lista de puncte
      p0  ;  /// punctul in functie de care se face sortarea tuturor punctelor
int n, i, j, pmi, m;
/// ret 0 daca punctele sunt coliniare, 1 daca sunt in ordine inversa trigonometrica (ceas), 2 altfel
int orientare(coord p, coord q, coord r)
{
    double x = (q.y-p.y)*(r.x-q.x) - (q.x-p.x)*(r.y-q.y);
    if(x==0)return 0;
    if(x>0)return 1;
    return 2;
}
/// returneaza patratul distantei intre doua puncte
double dist(coord p, coord q)
{
    return (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y);
}
int cmp(coord p, coord q)
{
    int o=orientare(p0, p, q);
    if(o==2)return 1;
    if(o==1)return 0;
    return dist(p0,q)>=dist(p0,p);
}
/// returneaza al doilea element din stiva
coord stivaDoi(stack <coord> s)
{
    coord vf = s.top();
    s.pop();
    coord doi=s.top();
    s.push(vf);
    return doi;
}
int main()
{
    fin >> n;
    for(i=1; i<=n; i++)
        fin >> p[i].x >> p[i].y;
    /// caut punctul de minim, daca-s mai multe pe cel mai din stanga
    pmi = 1;
    for(i=2; i<=n; i++)
        if(p[i].y<p[pmi].y || (p[i].y==p[pmi].y && p[i].x<p[pmi].x))pmi = i;
    /// pun punctul la inceput
    swap(p[1],p[pmi]);
    p0=p[1];
    sort(p+2, p+n+1,cmp);/// sortez restul punctelor

    m=1; /// modific lista de puncte, si psatrez doar pe cele care merita
    for(i=2; i<=n; i++)
    {
        //while(i<n && orientare(p0, p[i], p[i+1])==0)i++;
        m++;
        p[m] = p[i];

    }
   // cout << m << "\n";
    //for(i=1; i<=m; i++) cout << p[i].x << " " << p[i].y << "\n";
    if(m<3)cout << "Nu merge";
    stiva.push(p[1]); stiva.push(p[2]); stiva.push(p[3]);
    for(i=4; i<=m; i++)
    {
        while(stiva.size()>1 && orientare(stivaDoi(stiva), stiva.top(), p[i])==1)
            {stiva.pop();}
        stiva.push(p[i]);
    }
    while(!stiva.empty())
    {
        coord a=stiva.top();
        stiva.pop(); af.push(a);
        //cout << a.x << " " << a.y << "\n";
    }
    fout << af.size() << "\n";
    fout << setprecision(6) << fixed;
    while(!af.empty())
    {
        coord a=af.top();
        af.pop();
        fout << a.x << " " << a.y << "\n";
    }
    return 0;
}