Cod sursa(job #3363343)

Utilizator david333Popescu David david333 Data 16 august 2026 16:56:16
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
vector <pair<double, double > > v;
vector <pair<double, double > > v2;
long long n, i, j, ind;
double x, y, mn = 1e18, x1, x2, x3, y1, y2, y3;
double determinant(double x1, double x2, double x3, double y1, double y2, double y3)
{
    return ((x1 * y2) + (y1 * x3) + (x2 * y3)) - ((y2 * x3) + (y1 * x2) + (x1 * y3));
}
double cmp( pair<double,double>& a, pair<double,double>& b)
{
    double det = (determinant(v[0].first, a.first, b.first, v[0].second, a.second, b.second));
    if(abs(det) <= 1e-9)
    {
        double d1 = (a.first-v[0].first)*(a.first-v[0].first) + (a.second-v[0].second)*(a.second-v[0].second);
        double d2 = (b.first-v[0].first)*(b.first-v[0].first) + (b.second-v[0].second)*(b.second-v[0].second);
        return d1 < d2;
    }
    return det > 0;
}
int main()
{
    cin>>n;
    v.push_back({1e6, 1e6});
    for(i=1; i<=n; i++)
    {
        cin>>x>>y;
        v.push_back({x, y});
        if(y < mn)
        {
            mn = y;
            v[0].first = x;
            v[0].second = y;
        }
    }
    sort(v.begin() + 1, v.end(), cmp);
    x1 = v[0].first;  y_1 = v[0].second;
    x2 = v[1].first;  y2 = v[1].second;
    v2.push_back({x1, y_1});
    v2.push_back({x2, y2});
   for(i=2; i<v.size(); i++)
   {
       x3 = v[i].first;
       y3 = v[i].second;
       while(v2.size() >= 2 && determinant(x1, x2, x3, y1, y2, y3) < 0 )
       {
           v2.pop_back();
           x2 = x1; y2 = y1;
           x1 = v2[v2.size()-2].first;
           y1 = v2[v2.size()-2].second;
       }
       v2.push_back({x3, y3});
        x1 = x2; y1 = y2;
        x2 = x3; y2 = y3;
   }
   cout<<v2.size()<<'\n';
   for(i=0; i<v2.size(); i++)
   {
        cout<<fixed<<setprecision(6)<<v2[i].first<<' ';
        cout<<fixed<<setprecision(6)<<v2[i].second<<'\n';
   }
    return 0;
}