Cod sursa(job #3159145)

Utilizator Vlad33333Vlad Lazar Vlad33333 Data 20 octombrie 2023 19:39:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

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

int n;

struct pct{
    double x,y;
}a[120001];
vector<pct> s;
vector<pct> q;

bool comp1(pct d,pct c)
{
    if(d.x==c.x)
        return d.y<c.y;
    else return d.x<c.x;
}

bool comp2(pct d,pct c)
{
    if(d.x==c.x)
        return d.y>c.y;
    else return d.x>c.x;
}

void citire()
{
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>a[i].x>>a[i].y;
}

int det(pct q,pct w,pct e)
{
    double l=(q.x*w.y)+(w.x*e.y)+(e.x*q.y)-(w.y*e.x)-(e.y*q.x)-(q.y*w.x);
    return l>0;
}

void inv1()
{
    for(int i=2;i<n;i++)
    {
       while(s.size() >= 2 && det(s[s.size()-2],s[s.size()-1],a[i]))
       {
           s.pop_back();
       }
       s.push_back(a[i]);
    }
}

void inv2()
{
    for(int i=n-3;i>=0;i--)
    {
       while(q.size() >= 2 && det(q[q.size()-2],q[q.size()-1],a[i]))
       {
           q.pop_back();
       }
       q.push_back(a[i]);
    }
}

int main()
{
    citire();
    sort(a,a+n-1,comp1);
    s.push_back(a[0]);
    s.push_back(a[1]);
    q.push_back(a[n-1]);
    q.push_back(a[n-2]);
    inv1();
    inv2();
    fout<<s.size()+q.size()-2<<endl;
    for(int i=q.size()-2;i>=0;i--)
        fout<<fixed<<setprecision(6)<<q[i].x<<" "<<q[i].y<<endl;
    for(int i=s.size()-2;i>=0;i--)
         fout<<fixed<<setprecision(6)<<s[i].x<<" "<<s[i].y<<endl;
    return 0;
}