Cod sursa(job #3222183)

Utilizator solicasolica solica solica Data 9 aprilie 2024 10:37:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

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

#define NMAX 1008
#define double long double

struct punct
{
    double x,y;
    bool operator == (punct const &a) const
    {
        return x==a.x && y==a.y;
    }
};

punct p0;

int n,i,j;
vector<punct>v;

int orientation (punct a, punct b, punct c)
{
    double v=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
    if (v<0)
    {
        return -1;///clockwise
    }
    if (v>0)
    {
        return 1; ///counter-clockwise
    }
    return 0;///collinear
}

bool cw (punct a, punct b, punct c, bool include_collinear)
{
    int orientare=orientation(a,b,c);
    return (orientare<0) || (include_collinear && orientare==0);
}

bool collinear (punct a, punct b, punct c)
{
    return (orientation(a,b,c)==0);
}

bool crt (punct a, punct b)
{
    int orientare=orientation(p0,a,b);
    if (orientare==0)
    {
        if ((p0.x-a.x)*(p0.x-a.x)+(p0.y-a.y)*(p0.y-a.y)<(p0.x-b.x)*(p0.x-b.x)+(p0.y-b.y)*(p0.y-b.y))
        {
            return 1;
        }
        return 0;
    }
    return orientare<0;
}

void convex_hull (vector<punct>&a, bool include_collinear = true)
{
    p0.y=100000005,p0.x=1000;
    for (auto it : a)
    {
        if (it.y<p0.y)
        {
            p0=it;
        }
        if (it.y==p0.y)
        {
            if (it.x<p0.x)
            {
                p0=it;
            }
        }
    }/// aflu punctul cel mai de jos
    sort (a.begin(),a.end(),crt);
    if (include_collinear)
    {
        int n=a.size()-1;
        while (n>=0 && collinear(p0,a[n],a.back()))
        {
            n--;
        }
        reverse(a.begin()+n+1,a.end());
    }
    vector <punct>stiva;
    for (auto it : a)
    {
        while (stiva.size()>1 && !cw(stiva[stiva.size()-2],stiva.back(),it,include_collinear))
        {
            stiva.pop_back();
        }
        stiva.push_back(it);
    }
    if (include_collinear==0 && stiva.size()==2 && stiva[0]==stiva[1])
    {
        stiva.pop_back();
    }
    a=stiva;
}

signed main()
{
    fin>>n;
    for (i=0; i<n; i++)
    {
        punct a;
        fin>>a.x>>a.y;
        v.push_back(a);
    }
    convex_hull(v);
    reverse(v.begin()+1,v.end());
    fout<<v.size()<<'\n';
    for (auto it : v)
    {
        fout<<fixed<<setprecision(12)<<it.x<<' '<<it.y<<'\n';
    }
    return 0;
}