Cod sursa(job #2525629)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 17 ianuarie 2020 17:07:53
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
#include <fstream>
#include <stack>
#include <stdlib.h>
#include <iomanip>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct Point
{
    double x, y;
};


Point p0;

Point nextToTop(stack<Point> &S)
{
    Point p = S.top();
    S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}

int swap(Point &p1, Point &p2)
{
    Point temp = p1;
    p1 = p2;
    p2 = temp;
}

int distSq(Point p1, Point p2)
{
    return (p1.x - p2.x)*(p1.x - p2.x) +
           (p1.y - p2.y)*(p1.y - p2.y);
}

int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;
    return (val > 0)? 1: 2;
}

int compare(const void *vp1, const void *vp2)
{
    Point *p1 = (Point *)vp1;
    Point *p2 = (Point *)vp2;

    int o = orientation(p0, *p1, *p2);
    if (o == 0)
        return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;

    return (o == 2)? -1: 1;
}


void convexHull(Point points[], int n)
{

    int ymin = points[0].y, min = 0;
    for (int i = 1; i < n; i++)
    {
        int y = points[i].y;


        if ((y < ymin) || (ymin == y &&
                           points[i].x < points[min].x))
            ymin = points[i].y, min = i;
    }

    swap(points[0], points[min]);


    p0 = points[0];
    qsort(&points[1], n-1, sizeof(Point), compare);


    int m = 1;
    for (int i=1; i<n; i++)
    {

        while (i < n-1 && orientation(p0, points[i],
                                      points[i+1]) == 0)
            i++;


        points[m] = points[i];
        m++;
    }

    if (m < 3) return;

    stack<Point> S;
    S.push(points[0]);
    S.push(points[1]);
    S.push(points[2]);

    for (int i = 3; i < m; i++)
    {
        while (orientation(nextToTop(S), S.top(), points[i]) != 2)
            S.pop();
        S.push(points[i]);
    }

    cout << fixed;
    cout << S.size() << '\n';
    while (!S.empty())
    {
        Point p = S.top();
        cout << setprecision(6) << p.x << ' ' << p.y << '\n';
        S.pop();
    }
}

int main()
{
    Point points[120005] ;
   int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> points[i].x >> points[i].y ;

    convexHull(points, n);
    return 0;
}