Cod sursa(job #1650665)

Utilizator Liviu98Dinca Liviu Liviu98 Data 11 martie 2016 19:42:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMax 120005
#define x first
#define y second
using namespace std;
ifstream g("infasuratoare.in");
ofstream f("infasuratoare.out");
typedef pair<double,double> Point;
int N,varf;
Point S[NMax],V[NMax];

void Citire()
{
    g>>N;
    for(int i=1;i<=N;i++)
        g>>V[i].x>>V[i].y;
}

inline double ProdusIncrucisat(Point A,Point B,Point C)
{
    return ((B.x-A.x)*(C.y-A.y))-((B.y-A.y)*(C.x-A.x));
}

inline int comp(Point p1,Point p2)
{
    return ProdusIncrucisat(V[1],p1,p2)<0;
}

void Sortare()
{
    int poz=1;
    for(int i=2;i<=N;i++)
        if(V[i]<V[poz])
        poz=i;

    swap(V[1],V[poz]);
    sort(V+2,V+N+1,comp);
}

void InfasurareConvexa()
{
    Sortare();
    S[1]=V[1];
    S[2]=V[2];
    varf=2;
    for(int i=3;i<=N;i++)
    {
        while(varf>=2 && ProdusIncrucisat(S[varf-1],S[varf],V[i])>0)
            varf--;
        S[++varf]=V[i];
    }
}

void Afisare()
{
    f<<fixed;
    f<<varf<<"\n";
    for(int i=varf;i>=1;i--)
        f<<setprecision(9)<<S[i].x<<' '<<S[i].y<<"\n";
}

int main()
{
    Citire();
    InfasurareConvexa();
    Afisare();
}