Cod sursa(job #2191175)

Utilizator VladGhetinaVlad Ghetina VladGhetina Data 1 aprilie 2018 22:05:33
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

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

#define l 123122

struct element
{
    double x , y;
}v[l],sol[l];

bool fr[l];
int n , k;

bool Cross_Product(double ax , double ay , double bx , double by , double cx , double cy)
{
    double x1 = ax-bx;
    double x2 = ax-cx;
    double y1 = ay-by;
    double y2 = ay-cy;

    return (y2*x1-y1*x2)>0;
}

void Solve()
{
    int i , pos , poz;
    double ax , ay , bx , by;
    double mny = 0 , mxx = 99999999;
    bool ok = 1 , flag;


    fin >> n;
    for ( i = 1 ; i <= n ; i ++ ){
        fin >> v[i].x >> v[i].y;
        if(mxx > v[i].x)
            mxx = v[i].x ,  mny = v[i].y , pos = i;
    }

    fr[pos] = 1;
    i = 1 , k = 1;
    while(i == pos)
      i++;
    pos = i;
    ax = mxx , ay = mny;
    sol[k].x = ax , sol[k].y = ay;
    bx = v[i].x , by = v[i].y;


    while(ok)
    {
        flag = 1;
        for ( i = 2 ; i <= n ; i ++ )
            if(!fr[i] && i != pos)
            {
                if(Cross_Product(ax,ay,bx,by,v[i].x,v[i].y))
                {
                    bx = v[i].x , by = v[i].y , poz = i , flag = 0;
                }
            }

        if (!flag){
            sol[++k].x = bx , sol[k].y = by , fr[poz] = 1 , pos = poz;
            ax = sol[k].x , ay = sol[k].y , bx = sol[k-1].x , by = sol[k-1].y;}
        else ok = 0;


    }

    fout << k <<'\n';

    for ( i = k ; i >= 1 ; i -- )
        fout << setprecision(12) << fixed << sol[i].x << " " << sol[i].y << '\n';
}

int main()
{
    Solve();
}