Pagini recente » Cod sursa (job #1996809) | Cod sursa (job #1289460) | Cod sursa (job #263845) | Cod sursa (job #1911064) | Cod sursa (job #1539221)
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>
using namespace std;
const double EPS = 1e-6;
const double INF = 1e200;
int N;
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
};
vector<Point> polygon, kernel;
struct Line {
double a, b, c;
Line(const Point& p1, const Point& p2)
: a(p1.y - p2.y),
b(p2.x - p1.x),
c(p1.x * p2.y - p2.x * p1.y) {}
};
double Area(const vector<Point>& p) {
double a = 0.0;
for (int i = 0; i < int(p.size()) - 1; ++i)
a += p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;
return a / 2.0;
}
void ReadPolygon() {
scanf("%d", &N);
polygon.resize(N + 1);
for (int i = 0; i < N; ++i)
scanf("%lf%lf", &polygon[i].x, &polygon[i].y);
polygon[N] = polygon[0];
if (Area(polygon) < 0)
reverse(polygon.begin(), polygon.end());
}
void GetBoundingBox() {
double minx = INF, maxx = -INF;
double miny = INF, maxy = -INF;
for (int i = 0; i < N; ++i) {
minx = min(minx, polygon[i].x);
maxx = max(maxx, polygon[i].x);
miny = min(miny, polygon[i].y);
maxy = max(maxy, polygon[i].y);
}
kernel.assign({Point(minx, miny), Point(maxx, miny),
Point(maxx, maxy), Point(minx, maxy)});
kernel.push_back(kernel[0]);
}
Point Intersection(const Line& l1, const Line& l2) {
double q = l1.a * l2.b - l2.a * l1.b;
double x = (l1.b * l2.c - l2.b * l1.c) / q;
double y = (l2.a * l1.c - l1.a * l2.c) / q;
return Point(x, y);
}
double Position(const Line& l, const Point& p) {
return l.a * p.x + l.b * p.y + l.c;
}
void CutKernel(const Line& l) {
vector<Point> new_kernel;
for (int i = 0; i < int(kernel.size()) - 1; ++i)
if (Position(l, kernel[i]) * Position(l, kernel[i + 1]) < -EPS) {
kernel.insert(kernel.begin() + i + 1,
Intersection(l, Line(kernel[i], kernel[i + 1])));
++i;
}
for (int i = 0; i < int(kernel.size()) - 1; ++i)
if (Position(l, kernel[i]) > -EPS)
new_kernel.push_back(kernel[i]);
new_kernel.push_back(new_kernel[0]);
kernel.swap(new_kernel);
}
int main() {
freopen("camera.in", "r", stdin);
freopen("camera.out", "w", stdout);
ReadPolygon();
assert(N != 3);
GetBoundingBox();
for (int i = 0; i < N; ++i)
CutKernel(Line(polygon[i], polygon[i + 1]));
printf("%.2f\n", Area(kernel));
return 0;
}