CGL_1_C Counter-Clockwise

Calendar Clock iconCalendar Clock icon

AOJ

Table of contents

# Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C

Classify relative positions of 2 vectors into 5.

  1. Counter-clockwise
  2. Clockwise
  3. Opposite directions
  4. Same directions (p1 is further)
  5. Same directions (p2 is further)

# Explanation

First, calculate cross product.
If cross product is negative, the answer is 1.
If positive, the answer is 2.
If 0, they are on a line and the answer is 3, 4 or 5.

Second, calculate dot product.
If dot product is negative, the answer is 3.
If not, 2 vectors are on the same direction and the answer is 4 or 5.

Finally, calculate the lengths of 2 vectors.

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define EPS 0.0000000001
#define fequals(a,b) (fabs((a) - (b)) < EPS)

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (const Vector2 v) const { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (const Vector2 v) const { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (const double k) const { return Vector2(x * k, y * k); }
  Vector2 operator / (const double k) const { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 const v) { return x * v.x + y * v.y; }
  double cross (Vector2 const v) { return x * v.y - y * v.x; }
  
  bool parallel(Vector2 &other) {
    return fequals(0, cross(other));
  }
  
  bool orthogonal(Vector2 &other) {
    return fequals(0, dot(other));
  }
  
  bool operator < (const Vector2 &v) {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}
Int N;
Vector2 p0, p1, p2, v01;
string msgs[5] = {"COUNTER_CLOCKWISE", "CLOCKWISE", "ONLINE_BACK", "ONLINE_FRONT", "ON_SEGMENT"};

int clk(Vector2 &v01, Vector2 &v02) {
  double cross_ = v01.cross(v02);
  if (cross_ > 0.0) return 0;
  else if (cross_ < 0.0) return 1;

  double dot_ = v01.dot(v02);
  if (v01.dot(v02) < 0.0) return 2;
  if (v01.length() - v02.length() >= 0) return 4;
  return 3;
}

void solve() {
  Vector2 v02 = p2 - p0;
  int msg_idx = clk(v01, v02);
  cout << msgs[msg_idx] << endl;
}

void input() {
  cin >> p0 >> p1 >> N;
  v01 = p1 - p0;
  while (cin >> p2) {
    solve();
  }
}

int main() {
  cout.precision(15);
  input();
}

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments