Cod sursa(job #3253697)

Utilizator tudor_costinCostin Tudor tudor_costin Data 4 noiembrie 2024 15:07:01
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define x first
#define y second
const int Nmax=1e4+5;
const long double eps=1e-12;
bool viz[Nmax];
pair<long double,long double> a[Nmax];
bool isright(pair<long double,long double> a,pair<long double,long double> b,pair<long double,long double> c)
{
    return eps>=(c.y-a.y)*(b.x-a.x)-(b.y-a.y)*(c.x-a.x);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    if(n==0) return 0;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].x>>a[i].y;
        viz[i]=0;
    }
    sort(a+1,a+n+1);
    vector<int> s;
    int top=0;
    int sgn=1;
    for(int i=1; i>=1; i+=sgn)
    {
        if(i==n) sgn=-1;
        if(viz[i]) continue;
        while(top>=2 && isright(a[s[top-2]],a[s[top-1]],a[i]))
        {
            viz[s[top-1]]=0;
            s.pop_back();
            top--;
        }
        s.push_back(i);
        if(i!=1) viz[i]=1;
        top++;
    }
    s.pop_back();
    cout<<s.size()<<'\n';
    cout<<setprecision(6)<<fixed;
    for(int i:s) cout<<a[i].x<<' '<<a[i].y<<'\n';
    return 0;
}