Cod sursa(job #1615645)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 26 februarie 2016 18:48:14
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>

using namespace std;

int n;

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

struct Point
{
    vec2 pos;
    double angle;
};

inline double getDistance(const vec2& a, const vec2& b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

inline double getDistanceSq(const vec2& a, const vec2& b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

inline double getAngle(const vec2& a)
{
    return atan2(a.y, a.x);
}

inline double getLength(const vec2& a)
{
    return sqrt(a.x * a.x + a.y * a.y);
}

inline vec2 getNorm(const vec2& a)
{
    double len = getLength(a);
    return vec2(a.x / len, a.y / len);
}

int pointComp(const void* aa, const void* bb)
{
    double d = ((Point*)aa)->angle - ((Point*)bb)->angle;
    if(d < 0)
        return -1;
    if(d > 0)
        return 1;
    return 0;
}

int mod(int pos)
{
    if(pos >= n)
        return pos - n;
    return pos;
}

double crossZ(const vec2& a, const vec2& b)
{
    return a.x * b.y - a.y * b.x;
}

int getSide(const vec2& a, const vec2& b, const vec2& m)
{
    vec2 amv(m.x - a.x, m.y - a.y);
    vec2 mbv(b.x - m.x, b.y - m.y);
    double res = crossZ(amv, mbv);
    if(res < 0)
        return -1;
    return 1;
}

int main()
{
    bool ok;
    double lmax = 0, l;
    int i, j, lres = 0, llmax = 0;
    Point* v;
    vec2* res, center(0, 0);
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f >> n;
    v = new Point[n];
    res = new vec2[n];
    for(i = 0; i < n; i++)
    {
        f >> v[i].pos.x >> v[i].pos.y;
        center.x += v[i].pos.x;
        center.y += v[i].pos.y;
        //v[i].angle = getAngle(v[i].pos);
    }
    center.x /= n;
    center.y /= n;
    for(i = 0; i < n; i++)
    {
        v[i].pos.x -= center.x;
        v[i].pos.y -= center.y;
        v[i].angle = getAngle(v[i].pos);
    }
    qsort(v, n, sizeof(Point), pointComp);
    lmax = getLength(v[i].pos);
    for(i = 1; i < n; i++)
    {
        l = getLength(v[i].pos);
        if(l > lmax)
        {
            lmax = l;
            llmax = i;
        }
    }
    res[0] = v[llmax].pos;
    lres = 1;
    for(i = llmax + 1; i < llmax + n; i++)
    {
        ok = true;
        for(j = lres - 2; j >= 0; j--)
        {
            if(getSide(res[j], v[mod(i)].pos, res[j + 1]) == 1)
            {
                break;
            }
            ok = false;
        }
        if(ok)
        {
            res[lres++] = v[mod(i)].pos;
        }
        else
        {
            lres = j + 2;
            res[lres++] = v[mod(i)].pos;
        }
    }
    lres--;
    g << lres << '\n';
    for(i = 0; i < lres; i++)
    {
        g << res[i].x + center.x << ' ' << res[i].y + center.y << '\n';
    }
    f.close();
    g.close();
    return 0;
}