Cod sursa(job #2115518)

Utilizator cella.florescuCella Florescu cella.florescu Data 26 ianuarie 2018 20:47:27
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e3;
const double EPS = 1e-6;
const double MAXCOORD = 1e5;

struct Point {
  double x, y;
  Point (double a, double b) : x(a), y(b) {}
};

struct Line {
  double a, b, c;
  Line (Point A, Point B) : a(B.y - A.y), b(A.x - B.x), c(A.y * B.x - A.x * B.y) {}
};

vector <Point> v, intrs;

inline int sgn(double value) {
  if (fabs(value) < EPS)
    return 0;
  if (value > 0)
    return 1;
  return -1;
}

inline double det(Point A, Point B, Point C) {
  return A.x * B.y + B.x * C.y + C.x * A.y - A.x * C.y - B.x * A.y - C.x * B.y;
}

inline double area(vector <Point> &polygon) {
  if (polygon.size() < 3U)
    return 0.0;
  double ans = det(polygon.back(), polygon.front(), {0, 0});
  for (int i = 1; i < (int) polygon.size(); ++i)
    ans += det(polygon[i - 1], polygon[i], {0, 0});
  return ans;
}

inline Point inters(Line d1, Line d2) {
  double x = (d1.b * d2.c - d1.c * d2.b) / (d1.a * d2.b - d1.b * d2.a);
  double y = (d1.c * d2.a - d1.a * d2.c) / (d1.a * d2.b - d1.b * d2.a);
  return {x, y};
}

void cut_from_polygon(Point P1, Point P2) {
  vector <Point> new_intrs;
  Line d(P1, P2);
  intrs.push_back(intrs[0]);
  for (int i = 1; i < (int) intrs.size(); ++i) {
    int sgn1 = sgn(det(P1, P2, intrs[i - 1])), sgn2 = sgn(det(P1, P2, intrs[i]));
    Point P = inters(d, Line(intrs[i - 1], intrs[i]));
    if (sgn1 * sgn2 == -1)
      new_intrs.push_back(P);
    if (sgn2 >= 0)
      new_intrs.push_back(intrs[i]);
  }
  intrs = new_intrs;
}

int main()
{
    int n;
    ifstream fin("camera.in");
    fin >> n;
    for (int i = 0; i < n; ++i) {
      double a, b;
      fin >> a >> b;
      v.push_back({a, b});
    }
    fin.close();
    v.push_back(v[0]);
    if (area(v) < 0)
      reverse(v.begin(), v.end());
    intrs.push_back({MAXCOORD, MAXCOORD});
    intrs.push_back({-MAXCOORD, MAXCOORD});
    intrs.push_back({-MAXCOORD, -MAXCOORD});
    intrs.push_back({MAXCOORD, -MAXCOORD});
    for (int i = 1; i < (int) v.size() && intrs.size() > 2U; ++i)
      cut_from_polygon(v[i - 1], v[i]);
    ofstream fout("camera.out");
    fout << setprecision(2) << fixed << fabs(area(intrs)) / 2.0;
    fout.close();
    return 0;
}