Cod sursa(job #2884024)

Utilizator pctirziuTirziu Petre pctirziu Data 2 aprilie 2022 11:30:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const double eps = 1.0e-14;
struct puncte
{
    double x, y;
};
stack <puncte> st;
puncte p[120005];
// 0 - coliniare
// 1 - counterclockwise
// -1 - clockwise
puncte nexttotop()
{
    puncte x = st.top();
    st.pop();
    puncte y = st.top();
    st.push(x);
    return y;
}
int ccw(puncte p, puncte q, puncte r)
{
    double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if(fabs(val) < eps)
        return 0;
    if(val >= eps)
        return -1;
    return 1;
}
double distanta(puncte x, puncte y)
{
    return (x.x - y.x) * (x.x - y.x) - (x.y - y.y) * (x.y - y.y);
}
int cmp(puncte x, puncte y)
{
    return (ccw(p[0], x, y) < 0);
}
int main()
{
    int n, i, j;
    cin >> n;
    cin >> p[0].x >> p[0].y;
   // p[0].x += 1005;
    //p[0].y += 1005;
    for(i = 1; i < n; i++){
        cin >> p[i].x >> p[i].y;
       // p[i].x += 1005;
        //p[i].y += 1005;
        if((p[i].y - p[0].y <= -eps) or (fabs(p[i].y - p[0].y < eps) and p[i].x - p[0].x <= -eps))
            swap(p[0], p[i]);
    }
    sort(p + 1, p + n, cmp);
    p[n] = p[0];
    st.push(p[0]);
    st.push(p[1]);
    for(i = 2; i < n; i++){
        while(st.size() >= 2 and ccw(nexttotop(), st.top(), p[i]) == 1)
            st.pop();
        st.push(p[i]);
    }
    cout << st.size() << "\n";
    stack <puncte> afis;
    cout << fixed << showpoint;
    cout << setprecision(6);
    cout << p[0].x << " " << p[0].y << "\n";
    while(st.size() > 1){
        cout << st.top().x  << " " << st.top().y << "\n";
        afis.push(st.top());
        st.pop();
    }
    /*while(!afis.empty()){
        cout << fixed << showpoint;
        cout << setprecision(6);
        cout << afis.top().x << " " << afis.top().y << "\n";
        afis.pop();
    }*/
    return 0;
}