Pagini recente » Cod sursa (job #1576679) | Cod sursa (job #1801990) | Cod sursa (job #2227376) | Cod sursa (job #2079174) | Cod sursa (job #1736008)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("aria.in");
ofstream fout("aria.out");
const double eps = 1e-12;
struct Point {
double x;
double y;
Point() : x(0) , y(0) { }
Point(double _x, double _y) : x(_x) , y(_y) { }
Point operator+(const Point& p) {
return Point(p.x + x, p.y + y);
}
Point operator-(const Point& p) {
return Point(x - p.x, y - p.y);
}
bool operator<(const Point& p) {
if( fabs(p.x - x) < eps )
return fabs(p.y - y) < eps ? false : y < p.y;
return x < p.x;
}
bool operator==(const Point& p) {
return fabs(p.x - x) < eps && fabs(p.y - y) < eps;
}
bool operator!=(const Point& p) {
return !(fabs(p.x - x) < eps && fabs(p.y - y) < eps);
}
bool operator>(const Point& p) {
if( fabs(p.x - x) < eps )
return fabs(p.y - y) < eps ? false : y > p.y;
return x > p.x;
}
double distance(const Point& p) {
return sqrt( (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y) );
}
double det(const Point& p1, const Point& p2) {
return x * p1.y + p1.x * p2.y + p2.x * y -
y * p1.x - p1.y * p2.x - p2.y * x;
}
friend ostream& operator<<(ostream& out, const Point& a) {
out << a.x << ' ' << a.y << '\n';
return out;
}
friend istream& operator>>(istream& in, Point& a) {
in >> a.x >> a.y;
return in;
}
};
struct Line {
double a;
double b;
double c;
Line() { }
Line(double _a, double _b, double _c) : a(_a), b(_b), c(_c) { }
Line(const Point& p1, const Point& p2) {
a = p1.y - p2.y;
b = p2.x - p1.x;
c = p1.x * p2.y - p1.y * p2.x;
}
//-1 coincid
//0 paralele
//1 se intersecteaza
int intersects(const Line& line) {
double d = a * line.b - b * line.a;
if(fabs(d) < eps)
return fabs(c - line.c) < eps ? -1 : 0;
return 1;
}
Point intersection(const Line& line) {
double d = a * line.b - b * line.a;
if(fabs(d) < eps) //paralele sau coincid
return Point(0, 0);
double d1 = b * line.c - c * line.b;
double d2 = -a * line.c + c * line.a;
return Point(d1 / d, d2 / d);
}
friend ostream& operator<<(ostream& out, const Line& p) {
out << p.a << ' ' << p.b << ' ' << p.c << '\n';
return out;
}
};
struct Segment {
Point p1;
Point p2;
Segment() : p1(0, 0), p2(0, 0) { }
Segment(Point _p1, Point _p2) : p1(_p1), p2(_p2) { }
bool contains(const Point& p) {
double dAP = p1.distance(p);
double dBP = p2.distance(p);
double dAB = p1.distance(p2);
return fabs(dAB - dAP - dBP) < eps;
}
friend ostream& operator<<(ostream& out, const Segment& seg) {
out << seg.p1 << seg.p2;
return out;
}
};
struct Poligon {
vector<Point> v;
double area;
Poligon() { }
struct Comparator {
Point pivot;
Comparator(Point _pivot) : pivot(_pivot) { }
bool operator()(const Point& p1, const Point& p2) {
return pivot.det(p1, p2) < 0;
}
};
double computeArea() {
area = 0;
if(v.size() <= 2)
return 0;
v.push_back(v[0]);
Point p(0, 0);
for(unsigned i = 0; i < v.size(); ++i)
area += p.det(v[i], v[i + 1]);
v.pop_back();
area = 0.5 * fabs(area);
return area;
}
//Graham Scan, ordine trigonometrica
Poligon convexHull() {
int piv = 0;
for(unsigned i = 1; i < v.size(); ++i)
if(v[piv] > v[i])
piv = i;
swap(v[piv], v[0]);
Comparator cmpU(v[0]);
sort(v.begin() + 1, v.end(), cmpU);
Poligon pol;
if(v.size() == 0) return pol;
pol.v.push_back(v[0]);
if(v.size() == 1) return pol;
pol.v.push_back(v[1]);
for(unsigned i = 2; i < v.size() ; ++i) {
int head = pol.v.size();
while(head >= 2 && pol.v[head - 2].det(pol.v[head - 1], v[i]) > eps)
pol.v.pop_back(), head--;
pol.v.push_back(v[i]);
}
reverse(pol.v.begin(), pol.v.end());
return pol;
}
friend ostream& operator<<(ostream& out, const Poligon pol) {
out << pol.v.size() << '\n';
out << fixed << setprecision(6);
for(Point p : pol.v)
out << p;
return out;
}
friend istream& operator>>(istream& in, Poligon& pol) {
int n; fin >> n;
for(int i = 1; i <= n ; ++i) {
Point p; in >> p;
pol.v.push_back(p);
}
return in;
}
};
int main() {
Poligon pol;
fin >> pol;
fout << fixed << setprecision(7);
fout << pol.computeArea() << '\n';
return 0;
}