Cod sursa(job #3032160)

Utilizator ArseniuVictorStefanArseniu Victor Stefan ArseniuVictorStefan Data 21 martie 2023 16:45:25
Problema Rubarba Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.35 kb
#include <stdio.h>
#include <algorithm>

#define NMAX (100000) // the max. no. of points

// returns the max. of x and y
double min(double x, double y)
{
    return x <= y ? x : y;
}

// a point
struct point_t
{
    int x, y;

    // subtract points coordinate by coordinate
    point_t operator-(const point_t& other) const
    {
        return { x - other.x, y - other.y };
    }

    // multiply the points as if they were complex numbers
    point_t operator*(const point_t& other) const
    {
        return { x * other.x - y * other.y, x * other.y + y * other.x };
    }
};

// returns whether or not A is smaller than B by Y and for equality by X
bool smaller(const point_t& a, const point_t& b)
{
    return (a.y < b.y) || (a.y == b.y && a.x < b.x);
}

// return the cross product p x q
long long cross(const point_t& p, const point_t& q)
{
    return p.x * 1ll * q.y - p.y * 1ll * q.x;
}

// return the length squared of p
long long len_squared(const point_t& p)
{
    return p.x * 1ll * p.x + p.y * 1ll * p.y;
}

// returns the conjugate of a complex number
point_t conjugate(const point_t& p)
{
    return { p.x, -p.y };
}

// rotate x around o by the direction given by r - o (note: the vector is also scaled by the inverse of the squared length of dir)
point_t rotate(const point_t& x, const point_t& o, const point_t& r)
{
    return (x - o) * conjugate(r - o);
}

// the no. of points
int n;

// the points
point_t p[NMAX];

// the order of the points
int ord[NMAX];

// the convex hull
int hull[NMAX];
int top;

void convex_hull()
{
    // find the lowest point
    int o = 0;
    for(int i = 0; i < n; i++)
    {
        if(smaller(p[i], p[o]))
            o = i;
        ord[i] = i;
    }

    // sort the points around o
    std::sort(ord, ord + n, [o](const int& i, const int& j)
    {
        if(i == o) return true;
        if(j == 0) return false;
        long long c = cross(p[i] - p[o], p[j] - p[o]);
        return (c > 0) || (c == 0 && len_squared(p[i] - p[o]) < len_squared(p[j] - p[o]));
    });

    // calculate the convex hull
    for(int k = 0; k < n; k++)
    {
        int i = ord[k];
        while(top >= 2 && cross(p[i] - p[hull[top - 1]], p[hull[top - 1]] - p[hull[top - 2]]) >= 0)
            top--;
        hull[top++] = i;
    }
}

// increment i around the hull
int inc(int i)
{
    if((++i) == top)
        return 0;
    return i;
}

// decrement i around the hull
int dec(int i)
{
    if((--i) < 0)
        return top - 1;
    return i;
}

// return the highest (point with biggest y) between hull[i] and hull[j] in the system of reference with origin hull[o] and rotated such that OX is hull[o]hull[o+1]
int highest(int i, int j, int o)
{
    // calculate the points rotated
    point_t p1 = rotate(p[hull[i]], p[hull[o]], p[hull[inc(o)]]);
    point_t p2 = rotate(p[hull[j]], p[hull[o]], p[hull[inc(o)]]);

    // return the one with bigger y coordinate
    return (p1.y >= p2.y ? i : j);
}

int leftmost(int i, int j, int o)
{
    // calculate the points rotated
    point_t p1 = rotate(p[hull[i]], p[hull[o]], p[hull[inc(o)]]);
    point_t p2 = rotate(p[hull[j]], p[hull[o]], p[hull[inc(o)]]);

    // return the one with bigger y coordinate
    return (p1.x <= p2.x ? i : j);
}

int rightmost(int i, int j, int o)
{
    // calculate the points rotated
    point_t p1 = rotate(p[hull[i]], p[hull[o]], p[hull[inc(o)]]);
    point_t p2 = rotate(p[hull[j]], p[hull[o]], p[hull[inc(o)]]);

    // return the one with bigger y coordinate
    return (p1.x >= p2.x ? i : j);
}

double area(int y, int left, int right, int o)
{
    // rotate the points
    point_t py = rotate(p[hull[y]], p[hull[o]], p[hull[inc(o)]]);
    point_t pleft  = rotate(p[hull[left]],  p[hull[o]], p[hull[inc(o)]]);
    point_t pright = rotate(p[hull[right]], p[hull[o]], p[hull[inc(o)]]);

    // calculate the area
    long long len = len_squared(p[hull[inc(o)]] - p[hull[o]]);
    long long dx = pright.x - pleft.x;
    long long dy = py.y;
    return dx * dy * 1.0 / len;
}

int main()
{
    // open the files
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);

    // read the points
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d %d", &p[i].x, &p[i].y);

    // calculate the convex hull
    convex_hull();

    // calculate the initial state
    int i = 0; // first vertex of the current edge
    int y = 1; // the vertex with biggest y coordinate
    int left = 0, right = 0; // leftmost and rightmost vertices

    // increment y until it is the highest
    while(highest(y, inc(y), i) != y)
        y = inc(y);

    // decrement left until it is the leftmost vertex
    while(leftmost(left, dec(left), i) != left)
        left = dec(left);

    // increment right until it is the rightmost vertex
    while(rightmost(right, inc(right), i) != right)
        right = inc(right);

    // find the current answer
    double ans = area(y, left, right, i);

    // find the other areas and find the best
    while((i = inc(i)) != 0)
    {
        // increment y
        while(highest(y, inc(y), i) != y)
            y = inc(y);

        // increment left
        while(leftmost(left, inc(left), i) != left)
            left = inc(left);

        // increment right
        while(rightmost(right, inc(right), i) != right)
            right = inc(right);

        // update ans
        ans = min(ans, area(y, left, right, i));
    }

    // print the answer and exit
    printf("%f\n", ans);
    return 0;
}