Cod sursa(job #3228287)

Utilizator alexxiacrisanCrisan Maria - Alexia alexxiacrisan Data 7 mai 2024 11:51:50
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

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

struct Point
{
    double x, y;
};

int orientare(double x1, double y1, double x2, double y2, double x3, double y3)
{
    double d = (y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1);
    return d < 0;
}

int partition(Point puncte[], int low, int high)
{
    Point pivot = puncte[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++)
    {
        if (orientare(puncte[0].x, puncte[0].y, puncte[j].x, puncte[j].y, pivot.x, pivot.y))
        {
            i++;
            swap(puncte[i], puncte[j]);
        }
    }
    swap(puncte[i + 1], puncte[high]);
    return (i + 1);
}

void quickSort(Point puncte[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(puncte, low, high);
        quickSort(puncte, low, pi - 1);
        quickSort(puncte, pi + 1, high);
    }
}

int main()
{
    int nr_pct, i;
    fin >> nr_pct;

    Point puncte[120000];
    for (i = 0; i < nr_pct; i++)
        fin >> puncte[i].x >> puncte[i].y;

    int pct_initial = 0;
    for (i = 1; i < nr_pct; i++)
        if (puncte[i].x < puncte[pct_initial].x) pct_initial = i;
        else if(puncte[i].x == puncte[pct_initial].x && puncte[i].y < puncte[pct_initial].y) pct_initial = i;

    swap(puncte[0], puncte[pct_initial]);

    quickSort(puncte, 1, nr_pct - 1);

    int solutie[120000], k;
    solutie[0] = 0;
    solutie[1] = 1;
    k = 2;

    for(i = 2; i<nr_pct; i++)
    {
        while(k>2 && orientare(puncte[solutie[k-2]].x, puncte[solutie[k-2]].y, puncte[solutie[k-1]].x, puncte[solutie[k-1]].y, puncte[i].x, puncte[i].y))
            k--;
        solutie[k++] = i;
    }

    for (int i = 0; i < k; i++)
        fout << puncte[solutie[i]].x << " " << puncte[solutie[i]].y << endl;
    return 0;
}