Cod sursa(job #2280027)

Utilizator emcerchezEmanuela Cerchez emcerchez Data 10 noiembrie 2018 11:05:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define NMAX 120004
using namespace std;

typedef pair<double, double> Point;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n;
Point P[NMAX]; //poligonul
Point S[NMAX]; //stiva
int vf;
void citire();
void sortare();
void afisare();
void convex_hull();

int main()
{
 citire();
 convex_hull();
 afisare();
 return 0;
}

void citire()
{int i;
 fin >> n;
 for (i = 0; i < n; ++i)
      fin >> P[i].x >> P[i].y;
}

double CP(const Point& P1, const Point& P2, const Point& P3)
{
 return (P2.x-P1.x)*(P3.y-P1.y)-(P2.y-P1.y)*(P3.x-P1.x);
}

int cmp(const Point& P1, const Point& P2)
{
 return CP(P[0], P1, P2) > 0;
}

void sortare()
{int poz = 1, i;
 for (i = 1; i < n; ++i)
       if (P[i] < P[poz])
           poz = i;
  swap(P[0], P[poz]);
  sort(P + 1, P + n, cmp);
}

void convex_hull()
{int i;
 sortare();
 S[1] = P[0]; S[2] = P[1]; vf = 2;
 for (i=2; i < n; ++i)
     {
      while (vf >= 2 && CP(S[vf-1],S[vf],P[i])<=0)
             vf--;
        S[++vf] = P[i];
    }
}

void afisare()
{int i;
 fout << fixed;
 fout << vf << "\n";
 for (i = vf; i >= 1; --i)
      fout<<setprecision(9)<<S[i].x<<" "<<S[i].y<<"\n";
}