Cod sursa(job #2334482)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 2 februarie 2019 17:49:17
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.22 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;

const int NMAX = 2005;
const int MAX = 1e5;
const int MIN = -MAX;
const ld EPS = 1e-6;

struct Point {
  ld x, y;
  Point () {}
  Point (ld _x, ld _y) : x (_x), y (_y) {}
};

struct Line {
  ld a, b, c;
  Line () {}
  Line (const Point _a, const Point _b) : a (_a.y - _b.y), b (_b.x - _a.x), c (_a.x * _b.y - _b.x * _a.y) {}
  Point intersect (const Line &other) {
    Point ret;
    ret.x =  (other.c * b - c * other.b) / (a * other.b - other.a * b);
    ret.y = (-other.c * a + c * other.a) / (a * other.b - other.a * b);
    return ret;
  }
};

ld det (Point a, Point b, Point c) {
  return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

int sign (ld x) {
  if (-EPS <= x && x <= EPS) return 0;
  return (x > 0) ? 1 : -1;
}

int n, m;
Point points[NMAX];
Point ans[2][NMAX];

void trigonOrder() {
  ld area = 0.0;
  for (int i = 1; i <= n; ++i) {
    area += det ({0, 0}, points[i], points[i + 1]);
  }
  area /= 2.0;

  if (sign (area) != -1) {
    points[n + 1] = points[1];
    return;
  }
  reverse (points + 1, points + n + 1);
  points[n + 1] = points[1];
}

template <class T> void uin (T &a, T b) {a = min (a, b);}
template <class T> void uax (T &a, T b) {a = max (a, b);}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

  freopen ("camera.in", "r", stdin);
  freopen ("camera.out", "w", stdout);

  ans[0][1] = {MAX, MAX};
  ans[0][2] = {MIN, MAX};
  ans[0][3] = {MIN, MIN};
  ans[0][4] = {MAX, MIN};
  scanf ("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf ("%lf%lf", &points[i].x, &points[i].y);
    uin (ans[0][1].x, points[i].x); uin (ans[0][1].y, points[i].y);
    uax (ans[0][2].x, points[i].x); uin (ans[0][2].y, points[i].y);
    uax (ans[0][3].x, points[i].x); uax (ans[0][3].y, points[i].y);
    uin (ans[0][4].x, points[i].x); uax (ans[0][4].y, points[i].y);
  }

  trigonOrder();

  ans[0][5] = ans[0][1];
  m = 4;

  int old = 1, now = 0;
  for (int i = 1; i <= n; ++i) {
    swap (old, now);
    Point curr = points[i];
    Point next = points[i + 1];

    int new_m = 0;
    for (int j = 1; j <= m; ++j) {
      Point a = ans[old][j];
      Point b = ans[old][j + 1];

      if (sign (det (curr, next, a) * det (curr, next, b)) < 0) { // intersecteaza latura ab
        ans[now][++new_m] = Line (a, b).intersect (Line (curr, next));
      }
      if (sign (det (curr, next, b)) >= 0) { // daca e pe partea buna
        ans[now][++new_m] = b;
      }
    }

    m = new_m;
    ans[now][m + 1] = ans[now][1];
  }

  ld area = 0.0;
  for (int i = 1; i <= m; ++i) {
    area += det ({0, 0}, ans[now][i], ans[now][i + 1]);
  }
  area /= 2.0;

  printf ("%.2f\n", area);

  fclose (stdin);
  fclose (stdout);

#ifdef LOCAL_DEFINE
  fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}