Cod sursa(job #2806130)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 13:21:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <algorithm>
#include <bitset>

using namespace std;
FILE* f, * g;

///sens trigonometric=sens antiorar
struct point
{
    double x, y;
}v[120002];
int s[120002];
int n, top;
bitset <120002>yes;

bool how(point a, point b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

void read()
{
    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);
}
///diferenta vectorilor p1p2 si p2p3
///daca e 0 punctele sunt coliniare
///<0 (punctele constituie o orientare in sensul invers acelor de ceasornic),
///>0 (in sensul acelor de ceasornic)
double scanareGhram(point a, point b, point c)
{
    return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
}

void solve()
{
    int ok = 1;
    s[++top] = 1;
    s[++top] = 2, yes[2] = 1;
    int i = 3;///indicele punctului care urmeaza sa fie verificat pentru a stabili daca se afla pe infasuratoare
    while (!yes[1])///nu s-a realizat cel mai optim poligon
    {
        while (yes[i])
        {
            if (i == n) ok = -1;
            i += ok;
        }
        while (top >= 2 && scanareGhram(v[s[top - 1]], v[s[top]], v[i]) > 0)
            yes[s[top]] = 0, --top;
        s[++top] = i, yes[i] = 1;
    }
}
void write()
{
    fprintf(g, "%d\n", top - 1);
    for (int i = top - 1;i >= 1;--i)
        fprintf(g, "%lf %lf\n", v[s[i]].x, v[s[i]].y);
}
int main()
{
    f = fopen("infasuratoare.in", "r");
    g = fopen("infasuratoare.out", "w");
    read();
    solve();
    write();
    fclose(f);
    fclose(g);
    return 0;
}