Cod sursa(job #2588354)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 24 martie 2020 18:05:08
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>
#define MAX 120000
#define INF 2e9

using namespace std;

struct Point
{
    double x;
    double y;
}v[MAX], stiva[MAX];

double crossProduct(Point a, Point b, Point c)
{
    double x1 = b.x - a.x;
    double y1 = b.y - a.y;
    double x2 = c.x - a.x;
    double y2 = c.y - a.y;

    return y2 * x1 - y1 * x2;
}

bool greaterDistance(Point a, Point b, Point c)
{
    double x1 = b.x - a.x;
    double y1 = b.y - a.y;
    double x2 = c.x - a.x;
    double y2 = c.y - a.y;

    return (x1 * x1 + y1 * y1) < (x2 * x2 + y2 * y2);
}

bool cmp(const Point &a, const Point &b)
{
    return crossProduct(v[1], a, b) < 0;
}

int main()
{
    int n;

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

    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    srand(time(NULL));

    fin >> n;

    int minPointX = 1;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i].x >> v[i].y;

        if(v[i].x < v[minPointX].x || (v[i].x == v[minPointX].x && v[i].y > v[minPointX].y))
            minPointX = i;
    }

    swap(v[1], v[minPointX]);
    sort(v + 2, v + 1 + n, cmp);

    stiva[1] = v[1];
    stiva[2] = v[2];
    int head = 2;

    for(int i = 3; i <= n; i++)
    {
        if(head >= 2 && crossProduct(stiva[head - 1], stiva[head], v[i]) > 0)
            head--;

        stiva[++head] = v[i];
    }

    fout << head << '\n';
    fout << fixed;
    fout.precision(12);

    while(head)
    {
        fout << stiva[head].x << " " << stiva[head].y << '\n';
        head--;
    }

    fin.close();
    fout.close();

    return 0;
}