Pagini recente » Cod sursa (job #2055818) | Cod sursa (job #876366) | Cod sursa (job #97976) | Cod sursa (job #2767321) | Cod sursa (job #3197350)
#include <bits/stdc++.h>
using namespace std;
using T = long double;
using Point = complex<T>;
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 abs(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;
}