Cod sursa(job #3228286)

Utilizator alexxiacrisanCrisan Maria - Alexia alexxiacrisan Data 7 mai 2024 11:44:53
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 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 main()
{
    int nr_pct, i, j;
    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]);
    for (i = 1; i < nr_pct; i++)
        for (j = i + 1; j < nr_pct; j++)
            if (orientare(puncte[0].x, puncte[0].y, puncte[i].x, puncte[i].y, puncte[j].x, puncte[j].y))
                swap(puncte[i], puncte[j]);

    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;
    }

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