Cod sursa(job #791083)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 22 septembrie 2012 20:50:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define INF 0x3f3f3f3f
#define MAX 131072
#define EPS 1e-12

using namespace std;

struct punct
{
    double x, y;
}p[MAX];

int pct, stk[MAX], ind[MAX], n;

double abs(double a)
{
    if(a > 0) return a;
    return -a;
}

bool LESS(double a, double b)
{
    return a + EPS < b;
}

bool EQUAL(double a, double b)
{
    return abs(a - b) < EPS;
}

bool cmp(int a, int b)
{
    return LESS((p[a].x - p[pct].x) * (p[b].y - p[pct].y), (p[b].x - p[pct].x) * (p[a].y - p[pct].y));
}

bool semn(int i1, int i2, int i3)
{
    return (p[i1].x * p[i2].y + p[i2].x * p[i3].y + p[i1].y * p[i3].x - p[i2].y * p[i3].x - p[i1].y * p[i2].x - p[i3].y * p[i1].x) > EPS;
}

int main()
{
    ifstream in("infasuratoare.in");
    in>>n;
    p[0].x = p[0].y = INF;
    for(int i = 1; i <= n; i++)
    {
        in>>p[i].x>>p[i].y;
        if(LESS(p[i].x, p[pct].x) || (EQUAL(p[i].x, p[i].y) && LESS(p[i].y, p[pct].y))) pct = i;
    }
    in.close();
    for(int i = 1; i <= n; i++)
        if(i != pct) ind[++ind[0]] = i;
    sort(ind + 1, ind + ind[0] + 1, cmp);
    stk[stk[0] = 1] = pct;
    for(int i = 1; i <= ind[0]; i++)
    {
        while(stk[0] >= 2 && semn(stk[stk[0] - 1], stk[stk[0]], ind[i])) stk[0]--;
        stk[++stk[0]] = ind[i];
    }
    stk[++stk[0]] = pct;
    ofstream out("infasuratoare.out");
    out<<stk[0] - 1<<"\n";
    for(int i = stk[0]; i > 1; i--)
        out<<fixed<<setprecision(6)<<p[stk[i]].x<<" "<<p[stk[i]].y<<"\n";
    out.close();
    return 0;
}