Cod sursa(job #2092435)

Utilizator cipri321Marin Ciprian cipri321 Data 21 decembrie 2017 18:11:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120005
#define x first
#define y second
#define e 0.000000000001
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
pair<double,double> P[DIM];
int n;
int S[DIM],top;
int VIZ[DIM];
double dreapta(pair<double,double> O, pair<double,double> A, pair<double,double> B)
{
    return ((A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y))<e;
}
int main()
{
    fi>>n;
    for(int i=1;i<=n;i++)
        fi>>P[i].x>>P[i].y;
    sort(P+1,P+n+1);
    S[1]=1,S[2]=2,top=2,VIZ[2]=1;
    for(int i=1;i<=n;i++)
    {
        if(VIZ[i])
            continue;
        while(top>=2&&dreapta(P[S[top - 1]], P[S[top]], P[i]))
            VIZ[S[top--]]=0;
        S[++top]=i;
        VIZ[i]=true;
    }
    for(int i=n;i>=1;i--)
    {
        if(VIZ[i])
            continue;
        while(top>=2&&dreapta(P[S[top - 1]], P[S[top]], P[i]))
            VIZ[S[top--]]=0;
        S[++top]=i;
        VIZ[i]=true;
    }
    fo<<top-1<<"\n";
    for(int i=1;i<top;i++)
        fo<<setprecision(6)<<fixed<<P[S[i]].x<< " "<<P[S[i]].y<<"\n";
    fi.close();
    fo.close();
    return 0;
}