Cod sursa(job #2974026)

Utilizator alexscanteieScanteie Alexandru alexscanteie Data 2 februarie 2023 22:11:54
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <assert.h>
#include <iomanip>
#include <vector>
#include <queue>
#define NMAX 120005

using namespace std;

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

struct Punct{
    float x,y;
};

int N;
Punct points[NMAX];
int orientation(Punct p, Punct q, Punct r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colineare
    return (val > 0)? 1: 2; // sens orar : trigonometric
}

void convexHull(Punct points[], int n)
{
    vector<Punct> hull;

    // Cel mai din stanga punct
    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;

    /* Incepeti din punctul cel mai din stanga, continuati sa va miscati in sens trigonometric pana ajungem din nou la punctul de pornire. */
    int p = l, q;
    do
    {
        // Add current point to result
        hull.push_back(points[p]);

        /*
        Cautati un punct 'q' astfel incat orientarea (p, q,x) sa fie in sens invers acelor de ceasornic pentru toate punctele 'x'. Ideea este de a tine evidenta ultimului punct cel mai vizitat in sens invers acelor de ceasornic din q. Daca orice punct 'i' este mai in sens invers acelor de ceasornic decat q, atunci actualizati q.
        */
        q = (p+1)%n;
        for (int i = 0; i < n; i++)
        {
           if (orientation(points[p], points[i], points[q]) == 2)
               q = i;
        }


        p = q;

    } while (p != l);  // While we don't come to first point
    fout<<hull.size()<<'\n';
    for (int i = 0; i < hull.size(); i++)
        fout  << setprecision(7) << fixed << hull[i].x << " " << hull[i].y << "\n";
}

int main(){
    fin>>N;

    assert(3<= N && N <= 120000);
    for(int i=0;i<N;i++){
        fin>>points[i].x>>points[i].y;
    }
    convexHull(points,N);

    return 0;
}