Cod sursa(job #1409396)

Utilizator ThomasFMI Suditu Thomas Thomas Data 30 martie 2015 15:06:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
using namespace std;

#define NMax 120005
#define X first
#define Y second

#define szup stup[0]
#define szdown stdown[0]

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;
pair<double,double> P[NMax];
int stup[NMax],stdown[NMax];

bool isUpper(int i,int j,int k,bool ok)
{
    double a,b;
    a = (P[j].Y-P[i].Y)/(P[j].X-P[i].X);
    b = P[i].Y - a * P[i].X;

    bool rez = true;
    if(a<0) rez = ok;

    if(P[j].X != P[i].X)
    {
        if(a*P[k].X + b < P[k].Y) return rez;
        return !rez;
    }
    else return true;
}

void solve_up(int i)
{
    while(szup > 1 && !isUpper(stup[szup-1],stup[szup],i,false)) szup--;
    stup[++szup] = i;
}

void solve_down(int i)
{
    while(szdown > 1 && !isUpper(stdown[szdown-1],stdown[szdown],i,true)) szdown--;
    stdown[++szdown] = i;
}

int main()
{
    int i;

    f>>n;
    for(i=1;i<=n;++i) f>>P[i].X>>P[i].Y;

    sort(P+1,P+n+1);

    stup[++szup] = 1;
    stdown[++szdown] = 1;

    for(i=2;i<n;++i)
    {
        if(isUpper(1,n,i,false)) solve_up(i);
        else solve_down(i);
    }

    stdown[++szdown] = n;

    for(i=1;i<=szdown;++i) g<<P[stdown[i]].X<<" "<<P[stdown[i]].Y<<"\n";
    for(i=szup;i>=2;--i) g<<P[stup[i]].X<<" "<<P[stup[i]].Y<<"\n";

    f.close();
    g.close();
    return 0;
}