Cod sursa(job #3245854)

Utilizator staicumateiStaicu Matei Octavian staicumatei Data 30 septembrie 2024 21:18:53
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n,l,d,i,poz,s[1200002];

struct pct
{
    double x,y;
    int d;
}v[1200002];

bool sortare(pct p,pct q)
{
    if(p.x<q.x)
        return true;
    if(p.x>q.x)
        return false;
    if(p.y<q.y)
        return true;
    if(p.y>q.y)
        return false;
}

double her(pct a,pct b,pct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}

int main()
{
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>v[i].x>>v[i].y;

    }
    sort(v+1,v+n+1,sortare);
    for(i=2; i<n; i++)
    {
        if(her(v[1],v[n],v[i])<=0)
        {
            v[i].d=1;
        }
        else
        {
            v[i].d=2;
        }
    }
    int nr=0;
    s[++nr]=1;
    for(i=2; i<=n; i++)
    {
        if(v[i].d==1 or i==n)
        {
            while(her(v[s[nr-1]],v[s[nr]],v[i])<0 and nr>1)
            {
                nr--;
            }
            s[++nr]=i;
        }
    }
    s[nr]=n;
    for(i=n-1; i>=1; i--)
    {
        if(v[i].d==2 or i==1)
        {
            while(her(v[s[nr-1]],v[s[nr]],v[i])<0 and nr>1)
            {
                nr--;
            }
            s[++nr]=i;
        }
    }
    g<<nr-1<<endl;
    for(i=2; i<=nr; i++)
    {
        g<<fixed<<setprecision(6)<<v[s[i]].x<<" "<<v[s[i]].y<<" "<<endl;
    }
    return 0;
}