Cod sursa(job #3214395)

Utilizator tudor_bustanBustan Tudor Gabriel tudor_bustan Data 14 martie 2024 09:06:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
    double x, y;
};
enum Orientare
{
    trigonometric,
    antitrigonometric,
};
Orientare calcOrientare(punct p1, punct p2, punct p3)
{
    double det=(p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
    if(det>0)
    {
        return trigonometric;
    }
    if(det<0)
    {
        return antitrigonometric;
    }
}
int main()
{
    punct a[120001];
    fout<<setprecision(6)<<fixed;
    int n;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>a[i].x>>a[i].y;
    }
    sort(a+1, a+n+1, [](punct a, punct b)
         {
             if(a.x>b.x || a.x==b.x && a.y>b.y)
             {
                 return false;
             }
             return true;
         });
    vector<int> sol, sol2;
    sol.push_back(1);
    sol.push_back(2);
    for(int i=3; i<=n; i++)
    {
        while(calcOrientare(a[sol[sol.size()-2]], a[sol[sol.size()-1]], a[i])==trigonometric)
        {
            sol.pop_back();
        }
        sol.push_back(i);
    }
    sol2.push_back(n);
    sol2.push_back(n-1);
    for(int i=n-2; i>=1; i--)
    {
        while(calcOrientare(a[sol2[sol2.size()-2]], a[sol2[sol2.size()-1]], a[i])==trigonometric)
        {
            sol2.pop_back();
        }
        sol2.push_back(i);
    }
    fout<<sol.size()+sol2.size()-2<<"\n";
    for(int i=0; i<sol.size(); i++)
    {
        fout<<a[sol[i]].x<<" "<<a[sol[i]].y<<"\n";
    }
    for(int i=1; i<sol2.size()-1; i++)
    {
        fout<<a[sol2[i]].x<<" "<<a[sol2[i]].y<<"\n";
    }
    return 0;
}