Cod sursa(job #2537626)

Utilizator ionut.birisBiris Ionut ionut.biris Data 3 februarie 2020 20:13:51
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;

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

const int NMAX = 120000;

struct punct
{
    float x,y;
};

int N;
punct Puncte[NMAX],Stiva[NMAX];
int Contor;
int cnt= 0;

stack < int > S;
void read()
{
    f >> N;
    for(int i = 1; i <= N; i++)
        f >> Puncte[i].x >> Puncte[i].y;

}

void interschimbare(punct a, punct b){
    punct t = a;
    a = b;
     b= t;
}

void sortare()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = i+1; j<=N; j++)
        {
            if(Puncte[i].y > Puncte[j].y)
                interschimbare(Puncte[i],Puncte[j]);
            else if(Puncte[i].y == Puncte[j].y)
                if(Puncte[i].x > Puncte[j].x)
                    interschimbare(Puncte[i],Puncte[j]);
        }
    }
}

int orientare(punct a,punct b,punct c){
    double rez = (a.x*b.y) + (b.x * c.y) + (c.x*a.y) - (b.y*c.x) - (c.y * a.x) - (a.y*b.x);
    if(rez < 0)
        return -1;
    if(rez > 0)
        return 1;
    return 0;
}

void ConvexHull()
{
    S.push(1);
    int a = 1;
    S.push(2);
    int b = 2;
    int c;
    cnt = 3;
    while(cnt <= N)
    {
        c = cnt;
        while(orientare(Puncte[a],Puncte[b],Puncte[c]) < 0){
            S.pop();
            S.push(c);
            b = c;
            cnt++;
            c = cnt;
        }
        if(orientare(Puncte[a],Puncte[b],Puncte[c]) >= 0){
            S.push(c);
            b = c;
            cnt++;
            c = cnt;
        }
    }


}
int main()
{
    read();
    sortare();
    ConvexHull();
    while(!S.empty()){
        cout << S.top() << " ";
        S.pop();
    }

    return 0;
}