Cod sursa(job #2869135)

Utilizator RobertlelRobert Robertlel Data 11 martie 2022 12:46:06
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct{
double x,y;
}a[150000],q[150000];
int n,i,poz,vf;

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

bool cmp(punct b,punct c)
{
    return produs(a[1],b,c)<0;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i].x>>a[i].y;
    }
    poz=1;
    for(i=2;i<=n;i++)
    {
        if(a[poz].x>a[i].x||(a[poz].x==a[i].x&&a[poz].y>a[i].y))
            poz=i;
    }
    swap(a[poz],a[1]);
    sort(a+2,a+n+1,cmp);
    q[1]=a[1];
    q[2]=a[2];
    vf=2;
    for(i=3;i<=n;i++)
    {
        while(vf>=2 && produs(q[vf-1],q[vf],a[i])>0)
            vf--;
        vf++;
        q[vf]=a[i];
    }
    g<<vf<<'\n';
    for(i=vf;i>=1;i--)
        g<<fixed<<setprecision(6)<<q[i].x<<" "<<q[i].y<<'\n';

    return 0;
}