Cod sursa(job #3197348)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 26 ianuarie 2024 16:38:24
Problema Aria Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.52 kb
#include <bits/stdc++.h>
using namespace std;

using T = long double;
using Point = complex<double>;

istream& operator>>(istream &in, Point &a){
    T x, y;
    in >> x >> y;
    a = Point(x, y);
    return in;
}

ostream& operator<<(ostream &out, Point &a){
    out << fixed << setprecision(10) << a.real() << " " << a.imag();
    return out;
}

const T eps = 1e-9;
const T pi = acos(-1);

namespace std {
    bool operator<(Point a, Point b) {
        if(fabs(a.real() - b.real()) < eps)
            return a.imag() < b.imag() - eps;
        return a.real() < b.real() - eps;
    }
}

T squaredDist(Point a, Point b){
    return norm(b - a);
}

T dist(Point a, Point b){///distance from a to b
    return abs(b - a);
}

T dot(Point a, Point b){
    return (conj(a) * b).real();
}

T cross(Point a, Point b){
    return (conj(a) * b).imag();
}

T det(Point a, Point b, Point c){///0 if collinear, positive if (a, b, c) in trigonometric order, negative otherwise
    return cross(b - a, c - a) / 2.0;
}

bool areCollinear(Point a, Point b, Point c){
    return abs(det(a, b, c)) < eps;
}

T angle(Point a, Point b){
    return arg(b - a);
}

vector <Point> halfConvex(vector <Point> v, int half)//half = 1 for upper, -1 for lower
{
    vector <Point> ans; 
    for(auto it:v)
    {
        while(ans.size() >= 2 && half * det(ans.end()[-2], ans.end()[-1], it) > eps)//change to -eps to eliminate collinear points
            ans.pop_back();
        ans.push_back(it);
    }
    return ans;
}

vector<Point> convexHull(vector<Point> v){///returns the convex hull in anti-trigonometric order from the leftmost point
    if(v.size() == 1)
        return v;
    sort(v.begin(), v.end());
    if(v.size() == 2)
        return v;
    auto upper = halfConvex(v, 1);
    auto lower = halfConvex(v, -1);
    auto ans = upper;
    for(int i = lower.size() - 2; i > 0; i--)
        ans.push_back(lower[i]);
    return ans;
}

T areaPolygon(vector <Point> points)
{
    T rez = 0;
    points = convexHull(points);
    points.push_back(points.front());
    for(int i = 0; i < points.size() - 1; i++)
        rez += det(Point(0, 0), points[i], points[i + 1]);
    return rez;
}

vector <Point> v;

int main()
{
#ifndef HOME
    freopen("aria.in", "r", stdin);
    freopen("aria.out", "w", stdout);
#endif
    int n;
    cin >> n;
    v.resize(n, Point(0, 0));
    for(int i = 0; i < n; i++)
        cin >> v[i];
    cout << fixed << setprecision(5) << areaPolygon(v);
    return 0;
}