Cod sursa(job #3352265)

Utilizator nicoleta_iancuIancu Nicoleta nicoleta_iancu Data 26 aprilie 2026 02:09:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include<fstream>
#include<algorithm>
#include<iostream>
#include<vector>
#include<iomanip>
#include<stack>
#define inf 1e9+1
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct {
    double x, y;
    punct() :x(0), y(0) {};
    punct(double i, double j) :x(i), y(j) {};
};
//produs determinanti:
// x1 y1 1
// x2 y2 1
// x3 y3 1
//arie => x3*y2+ x2*y1+ x1*y3
//      - x3*y1+ x2*y3 + x1*y2
//      =>x3(y2-y1)+x2(y1-y3)+ x1(y3-y2)

double calcArieTriunghi(punct a, punct b, punct c) {
    return (c.x * (b.y - a.y) + b.x * (a.y - c.y) + a.x * (c.y - b.y)) ;
}

punct start= punct(inf,inf);//in functie de punctul asta vom sorta toate punctele
//trebuie ca punctul asta sa apartina infasuratorii ,deci il luam cel mai din stanga (apoi cel mai de jos)  punct

double calcPanta(punct& p1, punct& p2) {
    return (p1.y - p2.y) / (p1.x - p2.x);
}

bool cmp(punct a, punct b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}


vector<punct> convexHull(vector<punct>& v,int sens) {
    sort(v.begin(), v.end(), cmp);//sortam in functie de panta formata cu punctul de incepur
    vector<punct>s;//un stack cu punctele de pe infasuratoarea convexa
    int stackSize = 0;
    for (int i = 0; i < v.size(); ++i) {
        while (stackSize >=2 && ((sens==1 && calcArieTriunghi(s[stackSize-2],s[stackSize-1],v[i])>=0)||(sens == -1 && calcArieTriunghi(s[stackSize - 2], s[stackSize - 1], v[i])<=0)))
        {
            s.pop_back();
            stackSize--;
        }
        s.push_back(v[i]);
        stackSize++;
    }
    return s;
}


int main() {
   int n;
    fin >> n;
    vector<punct>v(n);
    int pozFound = 0;
    for (int i = 0; i < n; ++i) {
          fin >> v[i].x >> v[i].y;
    }

    vector<punct>upperHalf;
    vector<punct>lowerHalf;
    upperHalf = convexHull(v, 1);
    lowerHalf = convexHull(v, -1);
    fout << upperHalf.size() + lowerHalf.size() - 2<< "\n";
    for (auto i : upperHalf) {
        fout << fixed << setprecision(6) << i.x << " " << i.y << "\n";
    }
    for (int i = lowerHalf.size() - 2; i >= 1; --i) {
        fout << fixed << setprecision(6) << lowerHalf[i].x << " " << lowerHalf[i].y << "\n";
    }
    return 0;
}