Cod sursa(job #1843538)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 8 ianuarie 2017 21:10:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

struct vec2
{
    double x, y;
    vec2(double xx, double yy) : x(xx), y(yy) {}
    vec2(double a = 0) : x(a), y(a) {}

    inline double len() const { return sqrt(x*x + y*y); }

    inline vec2& normalize() {
        double l = len();
        x /= l; y /= l;
    }

    inline double dot(const vec2& a) const { return x * a.x + y * a.y; }
    inline double crossZ(const vec2& a) const { return x * a.y - y * a.x; }
    inline vec2 operator+(const vec2& a) const { return vec2(x + a.x, y + a.y); }
    inline vec2 operator-(const vec2& a) const { return vec2(x - a.x, y - a.y); }
} v[120001];

inline double crossZ(const vec2& a, const vec2& b) { return a.crossZ(b); }

bool cmp(const vec2& a, const vec2& b)
{
    return crossZ(a - v[0], b - v[0]) > 0;
}

int n;
int h[120001], lh;

int main()
{
    vec2 vaux;
    int i, j;
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        scanf("%lf%lf", &v[i].x, &v[i].y);
        if(v[i].x < v[0].x || (v[i].x == v[0].x && v[i].y < v[0].y))
        {
            vaux = v[0];
            v[0] = v[i];
            v[i] = vaux;
        }
    }
    sort(v + 1, v + n, cmp);
    h[0] = 0;
    h[1] = 1;
    lh = 2;
    for(i = 2; i < n; i++)
    {
        while(crossZ(v[i] - v[h[lh - 2]], v[h[lh - 1]]- v[h[lh - 2]]) > 0)
            lh--;
        h[lh++] = i;
    }
    printf("%d\n", lh);
    for(i = 0; i < lh; i++)
    {
        printf("%lf %lf\n", v[h[i]].x, v[h[i]].y);
    }
    return 0;
}