Cod sursa(job #2806131)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 13:22:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb

#include <stdio.h>
#define NMAX 120002
#include <bitset>
#include <algorithm>

using namespace std;
FILE* f, * g;

struct bla
{
    double x, y;
}v[NMAX];
int s[NMAX];
bitset <NMAX> viz;

bool how(bla A, bla B)
{
    if (A.x == B.x)
        return A.y < B.y;
    return A.x < B.x;
}
double determinant(bla A, bla B, bla C)
{
    double a = A.x, b = A.y, c = B.x, d = B.y, e = C.x, f = C.y;
    double delta = a * d + c * f + e * b - d * e - a * f - c * b;
    return delta;
}
void make(int n, int& top)
{
    int ok = 1, i;
    s[1] = 1;
    s[2] = 2, viz[2] = 1;
    top = 2;
    i = 3;
    while (!viz[1])
    {
        while (viz[i])
        {
            if (i == n) ok = -1;
            i += ok;
        }
        while (determinant(v[s[top - 1]], v[s[top]], v[i]) < 0 && top >= 2)
            viz[s[top]] = 0, --top;
        ///delta=0, punctele sunt coliniare
        ///delta<0, punctele constituie o orientare in sensul invers acelor de ceasornic
                    ///sens trigonometric
        ///delta>0, punctele constituie o orientare in sensul acelor de ceasornic
        s[++top] = i;
        viz[i] = 1;
    }
    --top;
}
int main()
{
    int top;
    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);
    make(n, top);
    fprintf(g, "%d\n", top);
    for (int i = 2;i <= top + 1;++i)
        fprintf(g, "%lf %lf\n", v[s[i]].x, v[s[i]].y);
    fclose(f);
    fclose(g);
    return 0;
}