Cod sursa(job #3148664)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 3 septembrie 2023 10:52:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.7 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <set>
#include <functional>
#include <bitset>
#include <map>
#include <unordered_map>
#include <queue>
#include <array>
#include <numeric>
#include <complex>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream& os, vector<A>& a) { for(auto &c:a)os<<c<<' '; return os;}
template<typename A> istream& operator>>(istream& os, vector<A>& a) { for(auto &c:a)os>>c; return os;}
template<typename A,size_t N> istream& operator>>(istream &os, array<A,N>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,typename B> istream& operator>>(istream& os, pair<A,B>&a) { os>>a.first>>a.second; return os;}
template<typename A> istream& operator >>(istream& os,complex<A>& a){pair<A,A>aux;os>>aux;a=complex<A>(aux.first,aux.second);return os;}
#define bug(a) cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define PQ priority_queue
#define x first
#define y second
using pii= pair<int,int>;
using VI= vector<int>;
using v64= vector<int64_t>;
using point=pair<double,double>;
using i64= int64_t;
using i16= int16_t;
using u64= uint64_t;
using u32= uint32_t;
using i32= int32_t;
using u16= uint16_t;
const i32 inf=1e9;
const i64 INF=1e18;
const int mod=1e9+7;
const int sigma=26;

double area(const point& p,const point& a,const point& b)
{
    return (a.x-p.x)*(b.y-p.y)-(b.x-p.x)*(a.y-p.y);
}
point second(stack<point>&x)
{
    auto aux=x.top();
    x.pop();
    auto rez=x.top();
    x.push(aux);
    return rez;
}
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
void solve()
{
    int n;
    cin>>n;
    vector<point>a(n);
    for(auto &c:a)
        cin>>c.first>>c.second;
    int it=min_element(all(a))-a.begin();
    auto aux=a[it];
    a.erase(a.begin()+it);
    n--;
    sort(all(a),[&](const point& x,const point& y){
        return area(aux,x,y)<0;
    });

    stack<point>b;
    b.push(aux);
    for(auto &c:a)
    {
        while(b.size()>1 && area(second(b),b.top(),c)>0)
        {
            b.pop();
        }
        b.push(c);
    }
    cout<<b.size()<<'\n';
    cout<<fixed<<setprecision(12);
    while(b.size())
    {
        cout<<b.top().x<<' '<<b.top().y<<'\n';
        b.pop();
    }



}
main()
{
    i32 tt=1;
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cin>>tt;
    while(tt--)
    {
        solve();
    }
}