Cod sursa(job #2765657)

Utilizator alexmorosanuMorosanu Alexandru alexmorosanu Data 29 iulie 2021 11:08:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("mosia1.in");
ofstream g("mosia1.out");
struct punct
{
    double x,y;
}a[120020],q[120020];
double cross_product(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 c,punct b)
{
    return cross_product(a[1],c,b)<0;
}
int n,i,pos,vf;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i].x>>a[i].y;
    pos=1;
    for(i=2;i<=n;i++)
        if(a[i].x<a[pos].x || (a[i].x==a[pos].x && a[i].y<a[pos].y))
            pos=i;
    swap(a[1],a[pos]);
    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 && cross_product(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';
}