Cod sursa(job #3364112)

Utilizator Andreea1501013Andreea Andreea1501013 Data 29 august 2026 23:27:28
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.37 kb
#include <bits/stdc++.h>
# define x first
# define y second

using namespace std;

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

pair<double,double> P[120005];
vector<pair<double, double>> sus, jos, sol1, sol2;
pair<double, double> A, B;
int N;

double detArie(pair<double, double> M, pair<double, double> N, pair<double, double> O)
{
    return (N.x - M.x) * (O.y - M.y) - (N.y - M.y) * (O.x - M.x);
}
void detJumatati()
{
    /// separ punctele in fct de pozitia lor fata de dreapta AB (sus sau jos)
    /// folosim formula ariei:
    /// S = 1/2 * (( Xa * Yp - Xp * Ya) + (Xp * Yb - Xb * Yp) + ( Xb * Ya - Xa * Yb)) =
    /// = 1/2 * ( Xa * (Yp - Yb) + Xb * (Ya - Yp) + Xp * (Yb - Ya))
    /// printr-un artificiu de calcul (sau cu determinanti) obtinem:
    /// 2S = (Xp - Xa) * (Yb - Ya) - (Yp - Ya) * (Xb - Xa)

    /// in fct de semnul acestei arii, pot vedea pe ce parte a dr AB este pct P
    /// S > 0 => P este jos
    /// S < 0 => P este sus

    for(int i = 1; i < N - 1; i++)
    {
        /// arie = 2S
        double arie = detArie(A, P[i], B);
        if(arie > 0)
        {
            jos.push_back(P[i]);
        }
        else
        {
            sus.push_back(P[i]);
        }
    }
    sus.push_back(B);
    jos.push_back(B);
}

void infasuratoare(vector<pair<double, double>> points, bool caz)
{
    if(points.empty() == 1)
    {
        return;
    }
    stack<pair<double,double>> inf;
    inf.push(A);
    pair<double,double> C;
    C = points[0];
    for(int i = 1; i < points.size(); i++)
    {
        double arie = detArie(inf.top(), C, points[i]);

        /// daca arie > 0 (pt infasuratoarea de sus) => am mers trigonometric => unghiul > 180 => pct C trebuie eliminat
        /// pt infasuratoarea de jos se schimba semnul

        while(inf.empty() == 0 && (caz == 0 && arie > 0) || (caz == 1 && arie < 0))
        {

            ///    top  points
            ///    /\  /
            ///   /  \/
            ///  /    C

            C = inf.top();
            inf.pop();
            if(inf.empty() == 0)
            {
                arie = detArie(inf.top(), C, points[i]);
            }
        }

        inf.push(C);
        C = points[i];
    }
    inf.push(B);
    while(inf.empty()==0)
    {
        if(caz == 0)
            sol1.push_back({inf.top().x, inf.top().y});
        else
            sol2.push_back({inf.top().x, inf.top().y});
        inf.pop();
    }
}

/*void afisare()
{
    for(int i = 0; i < sol1.size(); i++)
    {
        cout<<setprecision(12)<< fixed<< sol1[i].x<<' '<<sol1[i].y<<'\n';
    }
    reverse(sol2.begin(), sol2.end());
    for(int i = 1; i + 1 < sol2.size(); i++)
    {
        fout<<setprecision(12)<< fixed<< sol2[i].x<<' '<<sol2[i].y<<'\n';
    }
}*/

int main()
{
    fin>>N;
    for(int i = 0; i < N; i++)
    {
        fin>>P[i].x>>P[i].y;
    }
    sort(P, P + N);
    A = P[0];
    B = P[N - 1];

    detJumatati();
    infasuratoare(sus, 0);
    infasuratoare(jos, 1);

    for(int i = 0; i < sol1.size(); i++)
    {
        fout<<setprecision(12)<< fixed<< sol1[i].x<<' '<<sol1[i].y<<'\n';
    }
    reverse(sol2.begin(), sol2.end());
    for(int i = 1; i + 1 < sol2.size(); i++)
    {
        fout<<setprecision(12)<< fixed<< sol2[i].x<<' '<<sol2[i].y<<'\n';
    }
  //  afisare();
    return 0;
}