Cod sursa(job #2756384)

Utilizator VladS23Vlad Seba VladS23 Data 31 mai 2021 11:53:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.87 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <deque>
#include <iomanip>

using namespace std;

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

const double eps = 1e-14;
const double INF = 1e9;

class POINT
{
private:
    double x, y;

public:
    POINT()
    {
        x = 0;
        y = 0;
    }
    POINT(double _x, double _y)
    {
        x = _x;
        y = _y;
    }
    POINT(const POINT &other)
    {
        *this = other;
    }

    double getx() { return x; }
    double gety() { return y; }
    void setxy(double _x, double _y)
    {
        x = _x;
        y = _y;
    }

    double dist(const POINT &other);
    double panta(const POINT &other);

    POINT mijloc(const POINT &other);

    bool operator==(const POINT &other)
    {
        return (fabs(this->x - other.x) < eps && fabs(this->y - other.y) < eps);
    }
    bool operator<(const POINT &other)
    {
        if (fabs(this->x - other.x) > eps)
            return this->x < other.x;
        return this->y < other.y;
    }

    friend POINT mijloc(const POINT &a, const POINT &b);
    friend double cp(const POINT &a, const POINT &b, const POINT &c);
    friend int ccw(const POINT &a, const POINT &b, const POINT &c);
    /*
            1 daca cp > 0
            -1 daca cp < 0
            0 daca cp = 0
    */
    friend bool coliniare(const POINT &a, const POINT &b, const POINT &c);
    friend bool point_in_box(const POINT &a, const POINT &b, const POINT &c);
    friend int lines_intersection(const POINT &p1, const POINT &p2, const POINT &p3, const POINT &p4, POINT &p0);
    friend bool segm_intersection(const POINT &p1, const POINT &p2, const POINT &p3, const POINT &p4);
    friend bool point_in_triangle(const POINT &p, const POINT &a, const POINT &b, const POINT &c);
};

double POINT::dist(const POINT &other)
{
    return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
}

double POINT::panta(const POINT &other)
{
    if (fabs(x - other.x) < eps)
        return INF;

    return (y - other.y) / (x - other.x);
}

POINT POINT::mijloc(const POINT &other)
{
    POINT m;
    m.x = (x + other.x) * 0.5;
    m.y = (y + other.y) * 0.5;

    return m;
}

POINT mijloc(const POINT &a, const POINT &b)
{
    POINT M;
    M.x = (a.x + b.x) * 0.5;
    M.y = (a.y + b.y) * 0.5;

    return M;
}

double cp(const POINT &a, const POINT &b, const POINT &c)
{
    return ((b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x));
}

int ccw(const POINT &a, const POINT &b, const POINT &c)
{
    double val_cp;
    val_cp = cp(a, b, c);
    if (fabs(val_cp) < eps)
        return 0;
    if (val_cp >= eps)
        return 1;
    return -1;
}

bool coliniare(const POINT &a, const POINT &b, const POINT &c)
{
    return (ccw(a, b, c) == 0);
}

bool point_in_box(const POINT &a, const POINT &b, const POINT &c)
{
    POINT L, R;
    L.x = min(a.x, b.x);
    L.y = min(a.y, b.y);
    R.x = max(a.x, b.x);
    R.y = max(a.y, b.y);

    if (L.x <= c.x && c.x <= R.x && L.y <= c.y && c.y <= R.y)
        return 1;
    return 0;
}

int lines_intersection(const POINT &p1, const POINT &p2, const POINT &p3, const POINT &p4, POINT &p0)
{
    int a1, b1, c1;
    int a2, b2, c2;

    a1 = p1.y - p2.y;
    b1 = p2.x - p1.x;
    c1 = p1.x * p2.y - p2.x * p1.y;

    a2 = p3.y - p4.y;
    b2 = p4.x - p3.x;
    c2 = p3.x * p4.y - p4.x * p3.y;

    if (fabs(a1 * b2 - a2 * b1) < eps)
    {
        if (fabs(a1 * c2 - a2 * c1) < eps)
            return -1; // coincid
        else
            return 0; // paralele
    }
    else
    {
        double a, b;

        p0.x = (-c1 * b2 + c2 * b1) / (a1 * b2 - a2 * b1);
        p0.y = (-a1 * c2 + a2 * c1) / (a1 * b2 - a2 * b1);

        return 1;
    }
}

bool segm_intersection(const POINT &p1, const POINT &p2, const POINT &p3, const POINT &p4)
{
    int ccw1, ccw2, ccw3, ccw4;
    ccw1 = ccw(p1, p2, p3);
    ccw2 = ccw(p1, p2, p4);
    ccw3 = ccw(p3, p4, p1);
    ccw4 = ccw(p3, p4, p2);

    if (ccw1 * ccw2 < 0 && ccw3 * ccw4 < 0)
        return 1;
    if ((ccw1 * ccw2 < 0 && ccw3 * ccw4 == 0) || (ccw3 * ccw4 < 0 && ccw1 * ccw2 == 0))
        return 1;
    if (ccw1 * ccw2 == 0 && ccw3 * ccw4 == 0)
        return (point_in_box(p1, p2, p3) || point_in_box(p1, p2, p4) || point_in_box(p3, p4, p1) || point_in_box(p3, p4, p2));
    return 0;
}

bool point_in_triangle(const POINT &p, const POINT &a, const POINT &b, const POINT &c)
{
    float x1, x2, x3;

    x1 = ccw(p, a, b);
    x2 = ccw(p, b, c);
    x3 = ccw(p, c, a);

    return !(((x1 < 0) || (x2 < 0) || (x3 < 0)) && ((x1 > 0) || (x2 > 0) || (x3 > 0)));
}

const int NMAX = 12e4;

POINT v[NMAX + 5];
POINT ll;
int st[NMAX + 5];

bool cmp(POINT &a, POINT &b)
{
    return (ccw(ll, a, b) > 0);
}

int main()
{
    int n;
    double x, y;

    cin >> n;
    cin >> x >> y;

    v[0].setxy(x, y);

    for (int i = 1; i < n; i++)
    {
        cin >> x >> y;
        v[i].setxy(x, y);
        if (fabs(y - v[0].gety()) < eps)
        {
            if (x - v[0].getx() <= -eps) // x este mai mic
                swap(v[0], v[i]);
        }
        else if (y - v[0].gety() <= -eps)
            swap(v[0], v[i]);
    }
    ll = v[0];
    v[n] = v[0];
    /*for (int i = 0; i < n; i++)
        cout << v[i].getx() << ' ' << v[i].gety() << '\n';*/
    sort(v + 1, v + n, cmp);

    st[0] = 0;
    st[1] = 1;

    int a, b, i = 2, top = 1;
    while (i <= n)
    {
        if (ccw(v[st[top - 1]], v[st[top]], v[i]) > 0)
        {
            st[++top] = i;
            i++;
        }
        else
            top--;
    }
    cout << top << '\n';
    for (int i = 0; i < top; i++)
    {
        cout << fixed << setprecision(6) << v[st[i]].getx() << ' ' << v[st[i]].gety() << '\n';
    }
    return 0;
}