Cod sursa(job #2641719)

Utilizator marinaoprOprea Marina marinaopr Data 12 august 2020 15:10:29
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <algorithm>
#include <stack>

#define NMAX 120005

using namespace std;

FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");

struct punct {double x; double y;} p[NMAX];
int n,vf,stiva[NMAX],i,imin;
double xmin,ymin;

bool comparare(punct A, punct B)
{
    if((A.y - ymin)*(B.x - xmin) <= (A.x - xmin) * (B.x - xmin))
        return 1;
    return 0;
}

bool turn(double x1, double y1, double x2, double y2, double x3, double y3)
{
    return ((x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) >= 0);
}

int main()
{

    fscanf(fin, "%d", &n);
    ymin = 1e9;
    for(i=1; i<=n; ++i)
    {
        fscanf(fin, "%lf%lf", &p[i].x, &p[i].y);

        if(p[i].y < ymin)
        {
            ymin = p[i].y;
            imin = i;
        }
        else
            if(p[i].y == ymin and p[i].x < p[imin].x)
                imin = i;
    }

    xmin = p[imin].x;
    stable_sort(p+1, p+n+1, comparare);

    stiva[1] = 1;
    stiva[2] = 2;
    vf = 2;
    for(i=3; i<=n; ++i)
    {
        while(vf>=2 and !turn(p[stiva[vf-1]].x, p[stiva[vf-1]].y, p[stiva[vf]].x, p[stiva[vf]].y, p[i].x, p[i].y)) //0->right, 1->left
            vf--;
        vf++;
        stiva[vf] = i;
    }

    fprintf(fout, "%d\n", vf);
    fprintf(fout, "%lf %lf\n", p[stiva[vf]].x, p[stiva[vf]].y);
    for(i=1; i<=vf-1; ++i)
        fprintf(fout, "%lf %lf\n", p[stiva[i]].x, p[stiva[i]].y);

    fclose(fin);
    fclose(fout);
    return 0;
}