Cod sursa(job #1539220)

Utilizator vladrochianVlad Rochian vladrochian Data 30 noiembrie 2015 15:17:46
Problema Camera Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#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 != 4);
   GetBoundingBox();

   for (int i = 0; i < N; ++i)
      CutKernel(Line(polygon[i], polygon[i + 1]));

   printf("%.2f\n", Area(kernel));
   return 0;
}