Cod sursa(job #3300689)

Utilizator paul.serbanSerban Paul paul.serban Data 18 iunie 2025 16:24:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{
    long double x, y;
};
long double distPoints(Point A, Point B){
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
int turn(Point p, Point c, Point n){
    long double x = (c.x - p.x) * (n.y - p.y) - (c.y - p.y) * (n.x - p.x);
    if(x < 0)
      return -1;
    else if(x > 0)
      return 1;
    return 0;
}
Point first;
bool polarSort(const Point& A, const Point& B){
     int u = turn(first, A, B);
     if(u > 0)
       return true;
     else if(u < 0)
       return false;
     return distPoints(first, A) < distPoints(first, B);
}
bool compare(const Point& A, const Point& B){
    return (A.y < B.y) || (A.y == B.y && A.x < B.x);
}
vector<Point> convex(vector<Point> Points){
    vector<Point> infas;
    first = *min_element(Points.begin(), Points.end(), compare);
    sort(Points.begin(), Points.end(), polarSort);
    for(int i = 0; i < Points.size(); i++){
        while(infas.size() > 1 && turn(infas[infas.size() - 2], infas[infas.size() - 1], Points[i]) <= 0)
            infas.pop_back();
        infas.push_back(Points[i]);
    }
    return infas;
}
int main()
{
    int n;
    Point tempPoint;
    fin >> n;
    vector<Point> Points, infas;
    for(int i = 0; i < n; i++){
        fin>> tempPoint.x >> tempPoint.y;
        Points.push_back(tempPoint);
    }
    infas = convex(Points);
    fout << infas.size() << '\n';
    for(int i = 0; i < infas.size(); i++){
        fout << fixed << setprecision(12) << infas[i].x << " " << infas[i].y << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}