SRM401 Div2 Easy

250

GCDで解けるらしい。

typedef complex<double> Point;

double dot(Point a, Point b)
{
  return (a.real() * b.real() + a.imag() * b.imag());
}

double cross(Point a, Point b)
{
  return (a.real() * b.imag() - a.imag() * b.real());
}

const int RIGHT = 1, LEFT = -1, FRONT = -2, BACK = 2, OTHER = 0;

int ccw(Point a, Point b, Point c)
{
  b -= a;
  c -= a;
  if( cross(b, c) < 0.0 )return RIGHT;
  if( cross(b, c) > 0.0 )return LEFT;
  if( dot(b, c) < 0.0 )return BACK;
  if( norm(b) < norm(c) )return FRONT;
  return OTHER;
}

class DreamingAboutCarrots {
public:
  int carrotsBetweenCarrots(int x1, int y1, int x2, int y2)
  {
    int cnt = 0;
    for (int x = 0; x <= 50; ++x) {
      for (int y = 0; y <= 50; ++y) {
        if (x == x1 && y == y1) continue;
        if (x == x2 && y == y2) continue;
        cout << ccw(Point(x1, y1), Point(x, y), Point(x2, y2)) << endl; // この行がないとWA, why...
        if (ccw(Point(x1, y1), Point(x, y), Point(x2, y2)) == FRONT) ++cnt;
      }     
    }
    return cnt;
  }
};