Cod sursa(job #3279502)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 23 februarie 2025 12:55:18
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

typedef pair <long double, long double> punct;

const int nmax=12e4+5;
int n, st[nmax];
punct v[nmax];

double det3 (punct a, punct b, punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

bool cmp (punct x, punct y)
{
    return det3(v[1],x,y)<0;
}

int main()
{
    fin >> n;
    for (int i=1; i<=n; i++)
        fin >> v[i].x >> v[i].y;
    int poz=1;
    for (int i=2; i<=n; i++)
    {
        if (v[i]<v[poz])
            poz=i;
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);
    st[1]=1;
    st[2]=2;
    int k=2;
    for (int i=3; i<=n; i++)
    {
        while (k>=2 && det3(v[st[k-1]],v[st[k]],v[i])>0)
            k--;
        st[++k]=i;
    }
    fout << k << '\n';
    for (int i=k; i>=1; i--)
        fout << fixed << setprecision(12) << v[st[i]].x << " " << v[st[i]].y << '\n';
}