Cod sursa(job #2641768)

Utilizator marinaoprOprea Marina marinaopr Data 12 august 2020 17:29:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 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.y - ymin))
        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;
    swap(p[1],p[imin]);
    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;

}