Cod sursa(job #2476189)

Utilizator Catalin2002Catalin Craciun Catalin2002 Data 18 octombrie 2019 11:49:03
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
using namespace std;

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

struct data{

float x;
float y;

}v[120005],minim ;

vector <data> w;

bool minimul(data a, data b)
{
    if(a.y==b.y)
        return a.x < b.x ;

    return a.y < b.y;

}

bool operator != (data a, data b)
{
    if(a.x==b.x&&a.y==b.y)
        return false;

     return true;
}

float latura(data a, data b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}

float unghi(float a, float b ,float c)
{
    return acos( (b*b + c*c - a*a) / (2*b*c) );
}

data unghiul_bun(int n,data a ,data b )
{

    data c,c_max;

    float max_unghi=0,unghi1;

    for(int i=1;i<=n;i++)
    {
        c=v[i];

        unghi1 = unghi(latura(b,c) , latura(a,b) , latura(a,c) );

        if(max_unghi < unghi1)
        {
            max_unghi=unghi1;
            c_max=c;
        }

    }

    return c_max;
}

int main()
{
    int n,h=0,i;

    data a,b,c;

    fin>>n;

     minim.x=1000000000;
     minim.y=1000000000;

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

        if(minimul(v[i],minim))
            minim=v[i];

    }

    b=minim;
    a=minim;

    a.x++;

    c=unghiul_bun(n,b,a);

    h++;

    w.push_back(minim);

    while(c!=minim)
    {
        h++;

        w.push_back(c);
        a=b;
        b=c;
        c=unghiul_bun(n,b,a);

    }


    fout<<h<<"\n";

    for(i=0;i<w.size();i++)
    {
        fout<<w[i].x<<" "<<w[i].y<<"\n";
    }





    return 0;
}