Cod sursa(job #3122494)

Utilizator HandoMihnea-Vicentiu Hando Data 19 aprilie 2023 13:55:59
Problema Aria Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.99 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back
#define mt make_tuple

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()
#define uniq(x) unique(all(x)), x.end()

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T, size_t N>
void re(array <T, N>& x);
template <class T> 
void re(vt <T>& x);

template <class T> 
void re(T& x) {
    cin >> x;
}

template <class T, class... M> 
void re(T& x, M&... args) {
    re(x); re(args...);
}

template <class T> 
void re(vt <T>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void re(array <T, N>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void wr(array <T, N> x);
template <class T> 
void wr(vt <T> x);

template <class T> 
void wr(T x) {
    cout << x;
}

template <class T, class ...M>  void wr(T x, M... args) {
    wr(x), wr(args...);
}

template <class T> 
void wr(vt <T> x) {
    for(auto it : x)
        wr(it, ' ');
}

template <class T, size_t N>
void wr(array <T, N> x) {
    for(auto it : x)
        wr(it, ' ');
}

template<class T, class... M>
auto mvt(size_t n, M&&... args) {
    if constexpr(sizeof...(args) == 1)
        return vector<T>(n, args...);
    else
        return vector(n, mvt<T>(args...));
}

void set_fixed(int p = 0) {
    cout << fixed << setprecision(p);
}

void set_scientific() {
    cout << scientific;
}

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

struct PT {
    double x, y;
    PT() {
        x = y = 0;
    }

    PT(double x, double y) : x(x), y(y) {}
    PT(const PT& p) : x(p.x), y(p.y) {}
    PT operator + (const PT& a) const {
        return PT(x + a.x, y + a.y);
    }
    PT operator - (const PT& a) const {
        return PT(x - a.x, y - a.y);
    }
    PT operator * (const double a) const {
        return PT(x * a, y * a);
    }

    friend istream& operator>> (istream &stream, PT& a){
        stream >> a.x >> a.y;
        return stream;
    }
};

// for sortings
struct cmp_x {
    bool operator()(const PT& a, const PT& b) const {
        return a.x < b.x || (a.x == b.x and a.y < b.y);
    }
};

struct cmp_y {
    bool operator()(const PT& a, const PT& b) const {
        return a.y < b.y;
    }
};

inline double dot(PT a, PT b) { 
    return a.x * b.x + a.y * b.y; 
}

inline double dist2(PT a, PT b) { 
    return dot(a - b, a - b); 
}

inline double cross(PT a, PT b) { 
    return a.x * b.y - a.y * b.x; 
}

inline double euclidean_dist(PT a, PT b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int orientation(PT a, PT b, PT c) {
    double v = cross(b - a, c - a);
    if (v < 0) return -1; //clockwise
    if (v > 0) return +1; // counter-clockwise
    return 0;
}

bool cw(PT a, PT b, PT c, bool include_collinear = false) {
    int o = orientation(a, b, c);
    return o < 0 || (include_collinear and o == 0);
}

bool collinear(PT a, PT b, PT c) { 
    return orientation(a, b, c) == 0; 
}

void convex_hull(vt <PT>& a, bool include_collinear = false) {
    // select the point with the lowest Y coord.
    PT p0 = *min_element(a.begin(), a.end(), [](PT a, PT b) {
        return make_pair(a.y, a.x) < make_pair(b.y, b.x);
    });

    /*sort the points by the angle relative to the bottom most
      point and the horizontal
    */
    sort(all(a), [&p0](const PT& a, const PT& b) {
        int o = orientation(p0, a, b);
        if (o == 0)
            return dist2(p0, a) < dist2(p0, b);
        return o < 0;
    });

    /* If you need to include the collinear points while doing a Graham scan, you need another step after sorting. 
    You need to get the points that have the biggest polar distance from P0 (these should be at the end of the sorted vector) and are collinear. 
    The points in this line should be reversed so that we can output all the collinear points, otherwise the algorithm would get the nearest point in this line and bail.
    This step shouldn't be included in the non-collinear version of the algorithm, otherwise you wouldn't get the smallest convex hull.
    */
    if (include_collinear) {
        int i = len(a) - 1;
        while (i >= 0 and collinear(p0, a[i], a.back())) i--;
        reverse(a.begin() + i + 1, a.end());
    }

    /* We iterate through each point one by one, 
    and make sure that the current point and the two before it make a clockwise turn, 
    otherwise the previous point is discarded, since it would make a non-convex shape. 
    Checking for clockwise or anticlockwise nature can be done by checking the orientation.
    */
    vt <PT> st;
    for (int i = 0; i < len(a); ++i) {
        while (len(st) > 1 && !cw(st[len(st) - 2], st.back(), a[i], include_collinear)) {
            st.pop_back();
        }
        st.pub(a[i]);
    }

    a = st;
}

void nearest_points(vt <PT>& a, vt <PT>& t, double& res, int l, int r) {
    /* if we have at most 3 points we check for every pair of points
       the minimum distance that we find
    */
    if (r - l <= 3) {
        for (int i = l; i < r; ++i)
            for (int j = i + 1; j < r; ++j)
                res = min(res, euclidean_dist(a[i], a[j]));
        sort(allp(a, l, r), cmp_y());
        return;
    }

    /* divide and conquer */
    int m = (l + r) / 2;
    double midx = a[m].x;
    nearest_points(a, t, res, l, m);
    nearest_points(a, t, res, m, r);

    /* merge the set the two halves to avoid an extra log */
    merge(allp(a, l, m), allp(a, m, r), t.begin(), cmp_y());
    copy(allp(t, 0, r - l), a.begin() + l);

   /* we check for the merged set the points in the rectangle of size ε x 2ε for a new minimum (if we have one) */
   int tsz = 0;
   for (int i = l; i < r; ++i) {
        if (abs(a[i].x - midx) < res) {
            for (int j = tsz - 1; j >= 0 && a[i].y - t[j].y < res; --j)
                res = min(res, euclidean_dist(a[i], t[j]));
            t[tsz++] = a[i];
        }
   }
}

double PolygonArea(const vt <PT>& a) {
    double res = 0;
    for (int i = 0, j = len(a) - 1; i < len(a); ++i) {
        res += (a[j].x + a[j].x) * (a[j].y - a[i].y);
        j = i;
    }
    return abs(res / 2.0);
}

void solve() {
    int n; re(n);
    vt <PT> v(n); re(v);
    set_fixed(5);
    wr(PolygonArea(v));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("aria");

    int t = 1;
    for(;t;t--) {
        solve();
    }
    
    return 0;
}