Cod sursa(job #2662269)

Utilizator codrinKTanase Codrin Octavian codrinK Data 23 octombrie 2020 19:14:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;

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

struct punct{
    double x, y;
}puncte[120005];

int n;

bool viz[120005];
double miniY=0x3f3f3f3f, miniX=0x3f3f3f3f;
int indMini;

vector<int>rez;

int cautareInitiala()
{
    for (int i=1; i<=n; ++i)
    {
        if (!viz[i])
            return i;
    }
}

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

double calcDist(punct a, punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void solve()
{
    bool gasit=false;;
    int last=cautareInitiala();
    while(true)
    {
        gasit=false;
        for (int i=1; i<=n; ++i)
        {
            if (!viz[i]&& i!=last)
            {
                if (calcDet(puncte[rez[rez.size()-1]],puncte[last],puncte[i])>0)
                    last=i, gasit=true;
                else if (calcDet(puncte[rez[rez.size()-1]],puncte[last],puncte[i])==0)
                {
                    if (calcDist(puncte[rez[rez.size()-1]],puncte[last])>calcDist(puncte[rez[rez.size()-1]],puncte[i]))
                    {
                            last=i;
                            gasit=true;
                    }
                }
            }
        }
        if (!gasit)
            return;
        rez.push_back(last);
        viz[last]=1;
        last=rez[0];
    }
}

int main()
{
    f >> n;
    for (int i=1; i<=n; ++i)
    {
        f >> puncte[i].x >> puncte[i].y;
        if (puncte[i].x<miniX)
            miniX=puncte[i].x, indMini=i, miniY=puncte[i].y;
        else if (puncte[i].x==miniX && puncte[i].y<miniY)
            miniY=puncte[i].y, indMini=i;
    }

    rez.push_back(indMini);
    viz[indMini]=true;
    solve();
    for (auto &v:rez)
    {
        g << puncte[v].x << ' ' << puncte[v].y << '\n';
    }
	return 0;

}