Cod sursa(job #904167)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 3 martie 2013 20:21:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define MAX 130000
using namespace std;

typedef struct
{
  double x, y;
} point;

point P[MAX];
int n, i, st, Max, S[MAX];
double X, Y;

bool out(int i1, int i2, int i3)
{
    return P[i1].x*P[i2].y + P[i2].x*P[i3].y + P[i3].x*P[i1].y - P[i3].x*P[i2].y - P[i1].x*P[i3].y - P[i2].x*P[i1].y > 0;
}

bool cmp(point i, point j)
{
    return (i.y - Y) * (j.x - X) < (j.y - Y) * (i.x - X);
}

int main()
{
    ifstream fi("infasuratoare.in");
    ofstream fo("infasuratoare.out");
    fi >> n;
    P[0].x = P[0].y = int(2e9);
    for(i = 1; i <= n; i++)
    {
        fi >> P[i].x >> P[i].y;
        if(P[i].x < P[Max].x or (P[i].x == P[Max].x and P[i].y < P[Max].y))
            Max = i;
    }
    X = P[Max].x; Y = P[Max].y;
    swap(P[1], P[Max]);
    sort(P+2, P+n+1, cmp);
    P[++n] = P[1];
    S[++st] = 1;
    for(i = 2; i <= n; i++)
    {
        while(st > 1 and out(S[st], S[st-1], i)) st--;
        S[++st] = i;
    }
    fo << setprecision(6) << fixed;
    fo << st-1 << "\n";
    for(i = 1; i < st; i++) fo << P[S[i]].x << " " << P[S[i]].y << "\n";
    return 0;
}