Cod sursa(job #885624)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 22 februarie 2013 10:48:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef struct punct {double x,y;} PUNCT;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int N,i;
PUNCT P[120001];
PUNCT S[120001];
PUNCT R[120001];
int ks,kr;

int cmp(PUNCT A, PUNCT B)
{
    if (A.y<B.y)
        return 1;
    if (A.y==B.y && A.x<B.x)
        return 1;
    return 0;
}

void citeste(PUNCT &P)
{
    fi>>P.x>>P.y;
}

void scrie (PUNCT P)
{
    fo<<fixed<<setprecision(6)<<P.x<<" "<<P.y<<"\n";
}

// verifica daca C este spre stanga fata de AB
int stanga(PUNCT A, PUNCT B, PUNCT C)
{
    double x1,x2,y1,y2;
    x1=B.x-A.x;
    y1=B.y-A.y;
    x2=C.x-B.x;
    y2=C.y-B.y;
    if (x1*y2-x2*y1>0.0)
        return 1;
    return 0;
}

int main()
{
    fi>>N;
    for (i=1;i<=N;i++)
        citeste(P[i]);
    sort(P+1,P+N+1,cmp);
    // se determina partea dreapta
    ks=0;
    for (i=1;i<=N;)
        if (ks<=1)
            S[++ks]=P[i++];
        else
            if (stanga(S[ks-1],S[ks],P[i]))
                S[++ks]=P[i++];
            else
                ks--;
    // se determina partea stanga
    kr=0;
    for (i=N;i>=1;)
        if (kr<=1)
            R[++kr]=P[i--];
        else
            if (stanga(R[kr-1],R[kr],P[i]))
                R[++kr]=P[i--];
            else
                kr--;
    fo<<ks+kr-2<<'\n';
    for (i=1;i<=ks;i++)
        scrie(S[i]);
    for (i=2;i<kr;i++)
        scrie(R[i]);
    fi.close();
    fo.close();
    return 0;
}