ACM Programming Competition practice program: Hotter Colder

hottercolder.cpp

// Hotter Colder: http://acm.student.cs.uwaterloo.ca/~acm00/010127/E.html

#include <iostream>
#include <list>
#include <cmath>

using namespace std;

///////////////////////////////////////////////////////////
// POINT
///////////////////////////////////////////////////////////

struct point {
  float x;
  float y;
};

__inline
point operator-(point a, point b) {
  point p = { a.x - b.x, a.y - b.y };
  return p;
}

__inline
point operator+(point a, point b) {
  point p = { a.x + b.x, a.y + b.y };
  return p;
}

__inline
point midpoint(point a, point b) {
  point p = { (a.x + b.x) / 2, (a.y + b.y) / 2 };
  return p;
}

__inline
point rot_45deg_cw(point p) {
  point p1 = { -p.y, p.x };
  return p1;
}

__inline
point rot_45deg_ccw(point p) {
  point p1 = { p.y, -p.x };
  return p1;
}

__inline
float det(point a, point b) {
  return a.x * b.y - b.x * a.y;
}

void print_point(point p) {
  cout << "(" << p.x << ", " << p.y << ")";
}

///////////////////////////////////////////////////////////
// LINE
///////////////////////////////////////////////////////////

// a: origin, b: another point
// point is above the line if (p - a) cross (b - a) > 0
struct line {
  point a;
  point b;
};

bool above_line(line* l, point p) {
  return det(p - l->a, l->b - l->a) > 0;
}

point line_line_intersection(line* l, point a, point b) {
  float x1 = l->a.x;
  float y1 = l->a.y;
  float x2 = l->b.x;
  float y2 = l->b.y;
  float x3 = a.x;
  float y3 = a.y;
  float x4 = b.x;
  float y4 = b.y;
  float x1x2 = x1 - x2;
  float x3x4 = x3 - x4;
  float y1y2 = y1 - y2;
  float y3y4 = y3 - y4;
  float x1y2y1x2 = x1 * y2 - y1 * x2;
  float x3y4y3x4 = x3 * y4 - y3 * x4;

  float d = x1x2 * y3y4 - y1y2 * x3x4;

  point pt = {
    (x1y2y1x2 * x3x4 - x1x2 * x3y4y3x4) / d,
    (x1y2y1x2 * y3y4 - y1y2 * x3y4y3x4) / d,
  };
  return pt;
}

line* get_line_hot(point a, point b) {
  point mid = midpoint(a, b);
  point dir = rot_45deg_cw(b - mid);
  line* l = new line();
  l->a = mid;
  l->b = mid + dir;
  return l;
}

line* get_line_cold(point a, point b) {
  point mid = midpoint(a, b);
  point dir = rot_45deg_ccw(b - mid);
  line* l = new line();
  l->a = mid;
  l->b = mid + dir;
  return l;
}

///////////////////////////////////////////////////////////
// POLYGON
///////////////////////////////////////////////////////////

typedef list<point> polygon;
typedef polygon::iterator p_iter;

float area(polygon* poly) {
  p_iter it = poly->begin();
  p_iter end = poly->end();

  if (it == end) return 0.0;

  point p0 = *it;

  float area2 = 0.0;

  while (true) {
    point a = *it;
    it ++;
    point b = *it;
    if (it == end) break;

    a = a - p0;
    b = b - p0;

    area2 += det(a, b);

    //cout << a.x << "," << a.y << "|" << b.x << "," << b.y << endl;
  }
  return abs(area2) / 2;
}

void intersect_line(polygon* poly, line* l) {
  p_iter it = poly->begin();
  p_iter end = poly->end();

  p_iter out_to_in;
  p_iter in_to_out;

  bool found_in = false;
  bool found_out = false;
  bool found_begin = false;
  bool found_end = false;
  bool reverse = false;

  point out_to_in_intersect;
  point in_to_out_intersect;

  bool loop = true;
  while (loop) {
    p_iter ita = it;

    point a = *it;
    it ++;
    point b = *it;

    if (it == end) {
      b = *poly->begin();
      loop = false;
    }

    bool a1 = above_line(l, a); // is a inside zone?
    bool b1 = above_line(l, b); // is b inside zone?

    if (a1 || b1) found_in = true;
    if (!a1 || !b1) found_out = true;

    if (!a1 && b1) {
      // outside -> inside
      out_to_in_intersect = line_line_intersection(l, a, b);
      out_to_in = ita;
      found_begin = true;
      if (found_end) reverse = false;
    }
    if (a1 && !b1) {
      // inside -> outside
      in_to_out_intersect = line_line_intersection(l, a, b);
      in_to_out = it;
      found_end = true;
      if (found_begin) reverse = true;
    }

    //cout << a1 << " " << b1 << endl;

    //cout << a.x << "," << a.y << "|" << b.x << "," << b.y << endl;
  }

  //cout << "reverse " << reverse << "; out_to_in_intersect ";
  //print_point(out_to_in_intersect);
  //cout << "; in_to_out_intersect ";
  //print_point(in_to_out_intersect);
  //cout << endl;

  if (found_in && !found_out) {
    //cout << "no changes needed" << endl;
    return;
  } else if (!found_in && found_out) {
    //cout << "all points are outside" << endl;
    point p0 = *poly->begin();
    poly->clear();
    poly->push_back(p0);
    return;
  }

  if (!reverse) {
    /*-
     *  p1  p2  p3  p4  p5  p6  p7  p8  p9  p10 p11
     *  IN  IN  IN              IN  IN  IN  IN  IN
     *          i_o ^^      ^^ o_i
     */
    p_iter after = out_to_in;
    after ++;

    p_iter it = poly->erase(in_to_out, after);
    poly->insert(it, in_to_out_intersect);
    poly->insert(it, out_to_in_intersect);
  } else {
    /*-
     *  p1  p2  p3  p4  p5  p6  p7  p8  p9  p10 p11
     *              IN  IN  IN  IN
     *      o_i ^^                  ^^ i_o
     */
    p_iter after = out_to_in;
    after ++;
    poly->erase(poly->begin(), after);
    poly->erase(in_to_out, poly->end());

    poly->push_front(out_to_in_intersect);
    poly->push_back(in_to_out_intersect);
  }
}

void print_poly(polygon* poly) {
  int i = 0;
  for (p_iter it = poly->begin(); it != poly->end(); it ++) {
    point p = *it;
    cout << i << ": ";
    print_point(p);
    cout << endl;
    i ++;
  }
  cout << endl;
  cout << "Area: " << area(poly) << endl;
}


int main(int argc, char** argv) {
  polygon* poly = new list<point>();

  point pts[] = {
    { 0, 0 },
    { 0, 10 },
    { 10, 10 },
    { 10, 0 }
  };

  for (int i = 0; i < 4; i ++) {
    poly->push_back(pts[i]);
  }

  point p0 = pts[0];

  float x;
  float y;
  char word[8];

  while (true) {
    string str;
    if (!getline(cin, str)) break;
    if (!sscanf(str.c_str(), "%f %f %s", &x, &y, word)) break;

    point p1 = { x, y };
    if (word[0] == 'H') {
      line* l = get_line_hot(p0, p1);
      intersect_line(poly, l);
    } else if (word[0] == 'C') {
      line* l = get_line_cold(p0, p1);
      intersect_line(poly, l);
    } else if (word[0] == 'S') {
      point p = *poly->begin();
      poly->clear();
      poly->push_back(p);
    }
    printf("%.2f\n", area(poly));
    p0 = p1;
  }

  //l = get_line_cold(pts[0], pts[2]);
  //intersect_line(poly, l);
  //print_poly(poly);
  //
  //l = get_line_hot(pts[2], pts[3]);
  //intersect_line(poly, l);
  //print_poly(poly);
  //
  //l = get_line_cold(pts[3], pts[0]);
  //intersect_line(poly, l);
  //print_poly(poly);
  //
  //l = get_line_hot(pts[0], pts[2]);
  //intersect_line(poly, l);
  //print_poly(poly);

  return 0;
}

//int main(int argc, char** argv) {
//  polygon* poly = new list<point>();
//
//  point pts[] = {
//    { 0, 5 },
//    { 0, 10 },
//    { 5, 10 },
//    { 10, 10 },
//    { 10, 5 },
//    { 10, 0 },
//    { 5, 0 },
//    { 0, 0 },
//    //{ 0, 3 }
//  };
//
//  for (int i = 0; i < 8; i ++) {
//    poly->push_back(pts[i]);
//  }
//
//  print_poly(poly);
//
//  point pd = { 2, 3 };
//  point pc = { 4, 4 };
//  line l1 = { pc, pd };
//
//  point pe = { 10, 4 };
//  point pf = { 9, 5 };
//  line l2 = { pe, pf };
//
//  intersect_line(poly, &l1);
//
//  print_poly(poly);
//
//  intersect_line(poly, &l2);
//
//  print_poly(poly);
//
//  return 0;
//}