Cod sursa(job #3359386)

Utilizator Andrei-Aaron_BudulanBudulan Andrei-Aaron Andrei-Aaron_Budulan Data 27 iunie 2026 17:24:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

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

struct Point
{
    double x;
    double y;
};

double crossProduct(Point A, Point B, Point C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

int main()
{
    int N;
    fin>>N;
    fout<<fixed<<setprecision(15);
    vector<Point> points(N);


    for (int i=0; i<N; i++)
    {
        fin>>points[i].x>>points[i].y;
    }
    sort(points.begin(),points.end(),
         [](Point a, Point b)
    {
        if (a.x != b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
        );


    vector<Point> hull;

    for (int i=0; i<N; i++)
    {
        if (hull.size()>=2)
            while(hull.size()>=2 && crossProduct(hull[hull.size()-2],hull[hull.size()-1],points[i])<=0)
                hull.pop_back();

        hull.push_back(points[i]);
    }


    int t=hull.size()+1;
    for (int i=N-2; i>=0; i--)
    {
        if (hull.size()>=t)
            while(hull.size()>=t && crossProduct(hull[hull.size()-2],hull[hull.size()-1],points[i])<=0)
                hull.pop_back();

        hull.push_back(points[i]);
    }
    hull.pop_back();
    fout<<hull.size()<<endl;
    for (int i=0; i<hull.size(); i++)
        fout<<hull[i].x<<" "<<hull[i].y<<endl;
    return 0;
}