Cod sursa(job #1603710)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 17 februarie 2016 18:50:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
#define Nmax 120001
#define Mval 1000000001
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N,M=0;
struct punct{double x,y;} V[Nmax],P,S[Nmax];
void citire()
{
    f>>N;
    int poz=1;
    for(int i=1;i<=N;++i)
    {
        f>>V[i].x>>V[i].y;
        if(V[i].x<V[poz].x||(V[i].x==V[poz].x&&V[i].y<V[poz].y)) poz=i;
    }
    punct aux;
    aux=V[poz];
    V[poz]=V[1];
    V[1]=aux;
}
double arie(punct A, punct B,punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int cmp(const punct &P1,const punct &P2)
{
    return arie(V[1],P1,P2)<0;
}
void Hull()
{
    sort(V+2,V+N+1,cmp);
    S[1]=V[1];
    S[2]=V[2];
    M=2;
    for(int i=3;i<=N;++i)
    {
        while(M>=2&&arie(S[M-1],S[M],V[i])>0) M--;
        S[++M]=V[i];
    }
}
void afis()
{
    g<<fixed;
    g<<M<<'\n';
    for(int i=M;i>=1;i--) g<<setprecision(12)<<S[i].x<<" "<<S[i].y<<'\n';
}
int main()
{
    citire();
    Hull();
    afis();
}