Cod sursa(job #1603695)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 17 februarie 2016 18:44:28
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 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;
    double mx=Mval,my=Mval;
    for(int i=1;i<=N;++i)
    {
        f>>V[i].x>>V[i].y;
        if(V[i].x<mx) mx=V[i].x,my=V[i].y,poz=i;
        else if(V[i].x==mx&&V[i].y<my) my=V[i].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);
}
bool 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<<M<<'\n';
    for(int i=M;i>=1;i--) g<<setprecision(12)<<S[i].x<<" "<<S[i].y<<'\n';
}
int main()
{
    citire();
    Hull();
    afis();
}