Cod sursa(job #2806133)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 13:22:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <algorithm>

using namespace std;
FILE* f, * g;

struct name
{
    double x, y;
}v[120002];
int sol[120002];
bool viz[120002];

bool how(name A, name B)
{
    if (A.x != B.x)
        return (A.x < B.x);
    return (A.y < B.y);
}
double det(int a, int b, int c)
{
    double x1, y1, x2, y2, x3, y3;
    x1 = v[a].x;
    y1 = v[a].y;
    x2 = v[b].x;
    y2 = v[b].y;
    x3 = v[c].x;
    y3 = v[c].y;
    double de = x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1;
    return de;

}
int main()
{
    f = fopen("infasuratoare.in", "r");
    g = fopen("infasuratoare.out", "w");
    int n;
    fscanf(f, "%d", &n);
    for (int i = 1;i <= n;++i)
        fscanf(f, "%lf %lf", &v[i].x, &v[i].y);
    sort(v + 1, v + n + 1, how);
    int ok = 1;
    sol[1] = 1;///jonglam cu indicii
    sol[2] = 2, viz[2] = 1;
    int poz = 3, ss = 2;
    while (!viz[1])
    {
        while (viz[poz])
        {
            if (poz == n)
                ok = -1;
            poz += ok;
        }
        while (ss >= 2 && det(sol[ss - 1], sol[ss], poz) < 0)
            viz[sol[ss]] = 0, --ss;
        sol[++ss] = poz;
        viz[poz] = 1;
    }
    fprintf(g, "%d\n", ss - 1);
    for (int i = 2;i <= ss;++i)
        fprintf(g, "%lf %lf\n", v[sol[i]].x, v[sol[i]].y);
    fclose(f);
    fclose(g);
    return 0;
}