Cod sursa(job #2768390)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 10 august 2021 16:25:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <bits/stdc++.h>
#define NMAX 120005
#define ld long double

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;
struct elem
{
    ld x, y;
}points[NMAX], s[NMAX];

ld det(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3)
{
    return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}

ld distance(ld x1, ld y1, ld x2, ld y2)
{
    return (x2 - x1) * (x2 - x1) - (y2 - y1) * (y2 - y1);
}

bool cmp(elem a, elem b)
{
    ld d = det(0, 0, a.x, a.y, b.x, b.y);
    if(d == 0)
    {
        int d1 = distance(0, 0, a.x, a.y);
        int d2 = distance(0, 0, b.x, b.y);
        return d1 > d2;
    }
    return d > 0;
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> points[i].x >> points[i].y;

    int mini = 1;
    for(int i = 2; i <= n; i++)
        if(points[i].y < points[mini].y || (points[i].y == points[mini].y && points[i].x < points[mini].x) )
            mini = i;

    points[0] = points[mini];
    swap(points[1], points[mini]);

    for(int i = 1; i <= n; i++)
        points[i].x -= points[0].x, points[i].y -= points[0].y;

    sort(points + 2, points + 1 + n, cmp);

    int i;
    for(i = 3; i <= n; i++)
        if(det(points[1].x, points[1].y, points[2].x, points[2].y, points[i].x, points[i].y))
            break;
    int j = 2;
    i--;
    while(i > j)
    {
        swap(points[i], points[j]);
        i--, j++;
    }

    s[1] = points[1];
    s[2] = points[2];
    int k = 2;

    for(int i = 3; i <= n; i++)
    {
        while(k >= 2 && det(s[k - 1].x, s[k - 1].y, s[k].x, s[k].y, points[i].x, points[i].y) <= 0)
            k--;
        s[++k] = points[i];
    }

    g << k << "\n";
    for(int i = 1; i <= k; i++)
        g << setprecision(12) << fixed << s[i].x + points[0].x << " " << s[i].y + points[0].y << "\n";

    return 0;
}