Cod sursa(job #3363346)

Utilizator david333Popescu David david333 Data 16 august 2026 16:58:37
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 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 long, double long > > v;
vector <pair<double long, double long > > v2;
long long n, i, j, ind;
double long x, y, mn = 1e18, x1, x2, x3, y_1, y2, y3;
double long determinant(double long x1, double long x2, double long x3, double long y_1, double long y2, double long y3)
{
    return ((x1 * y2) + (y_1 * x3) + (x2 * y3)) - ((y2 * x3) + (y_1 * x2) + (x1 * y3));
}
double long cmp( pair<double long,double long>& a, pair<double long,double long>& b)
{
    double long det = (determinant(v[0].first, a.first, b.first, v[0].second, a.second, b.second));
    if(abs(det) <= 1e-12)
    {
        double long d1 = (a.first-v[0].first)*(a.first-v[0].first) + (a.second-v[0].second)*(a.second-v[0].second);
        double long 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<(long long)v.size(); i++)
   {
       x3 = v[i].first;
       y3 = v[i].second;
       while(v2.size() >= 2 && determinant(x1, x2, x3, y_1, y2, y3) < 0 )
       {
           v2.pop_back();
           x2 = x1; y2 = y_1;
           x1 = v2[v2.size()-2].first;
           y_1 = v2[v2.size()-2].second;
       }
       v2.push_back({x3, y3});
        x1 = x2; y_1 = y2;
        x2 = x3; y2 = y3;
   }
   cout<<v2.size()<<'\n';
   for(i=0; i<(long long)v2.size(); i++)
   {
        cout<<fixed<<setprecision(6)<<v2[i].first<<' ';
        cout<<fixed<<setprecision(6)<<v2[i].second<<'\n';
   }
    return 0;
}