UVa 10406 - Cutting tabletops

Accepted date: 2016-06-19
Run Time: 0.000
Ranking (as of 2016-06-19): 115 out of 411
Language: C++

/*
  UVa 10406 - Cutting tabletops

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10406_Cutting_tabletops.cpp
*/

#include <algorithm>
#include <vector>
#include <iterator>
#include <limits>
#include <cstdio>
#include <cmath>
using namespace std;

const double epsilon = numeric_limits<float>::epsilon();

struct point {
  double x_, y_;

  point() {}
  point(double x, double y) : x_(x), y_(y) {}
  point(const point &p) : x_(p.x_), y_(p.y_) {}
  bool operator==(const point& p) const {
    return fabs(x_ - p.x_) <= epsilon && fabs(y_ - p.y_) <= epsilon;
  }
};

double euclidean_distance(const point& a, const point& b)
{
  double dx = a.x_ - b.x_, dy = a.y_ - b.y_;
  return sqrt(dx * dx + dy * dy);
}

double cross_product(const point& o, const point& a, const point& b)
{
  return (a.x_ - o.x_) * (b.y_ - o.y_) - (b.x_ - o.x_) * (a.y_ - o.y_);
}

void get_cut_points(double d, const point& p, const point& q, point& cp, point& cq)
{
  double x = p.y_ - q.y_, y = q.x_ - p.x_, t = d / euclidean_distance(p, q);
  cp.x_ = p.x_ + x * t; cp.y_ = p.y_ + y * t;
    // cp(p.x_ + d * cos(theta), p.y_ + d * sin(theta)), 
    // cos(theta) = x / distance(p, q), sin(theta) = y / distance(p, q)
  cq.x_ = q.x_ + x * t; cq.y_ = q.y_ + y * t;
}

point get_intersect_points(const point& p1, const point& p2, const point& q1, const point& q2)
{
  double hq1 = cross_product(p1, p2, q1), hq2 = cross_product(p2, p1, q2);
    // fabs(hq1) is the distance between q1 and the vector p1 -> p2,
    // fabs(hq2) is the distance between q2 and the vector p2 -> p1
  double hq = hq1 + hq2;
    return point((q1.x_ * hq2 + q2.x_ * hq1) / hq, (q1.y_ * hq2 + q2.y_ * hq1) / hq);
}

double polygon_area(int n, const vector<point>& polygon)
{
  double area = 0.0;
  for (int i = 0; i < n; i++)
    area += polygon[i].x_ * polygon[(i + 1) % n].y_ - polygon[(i + 1) % n].x_ * polygon[i].y_;
  return area / 2.0;
}

#ifdef DEBUG
void print_polygon(int n, const vector<point>& polygon)
{
  for (int i = 0; i < n; i++)
    printf("(%.3lf, %.3lf)%c", polygon[i].x_, polygon[i].y_, ((i < n - 1) ? ' ' : '\n'));
}
#endif

int main()
{
  while (true) {
    double d;
    int n;
    scanf("%lf %d", &d, &n);
    if (d == 0.0 && n == 0)
      break;
    vector<point> points(n);
    for (int i = n - 1; i >= 0; i--)
      scanf("%lf %lf", &points[i].x_, &points[i].y_);
    vector<point> cpoints(n * 2);
    for (int i = 0; i < n; i++)
      get_cut_points(d, points[i], points[(i + 1) % n], cpoints[i * 2], cpoints[i * 2 + 1]);
#ifdef DEBUG
    print_polygon(n * 2, cpoints);
#endif
    for (int i = 0; i < n; i++)
      points[i] = get_intersect_points(cpoints[i * 2], cpoints[i * 2 + 1],
        cpoints[(i * 2 + 2) % (n * 2)], cpoints[(i * 2 + 3) % (n * 2)]);
#ifdef DEBUG
    print_polygon(n, points);
#endif
    printf("%.3lf\n", polygon_area(n, points));
  }
  return 0;
}