# Problem

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

Find a cross point of given 2 segments.

# Explanation

Algorithm to find cross point of 2 segments

# Solution

C++

// 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, p3;

Vector2 crossPoint() {
  Vector2 baseSeg = p1 - p0;
  Vector2 crossSeg = p3 - p2;
  double h1 = fabs(baseSeg.cross(p2 - p0)) / (baseSeg.length() * 2);
  double h2 = fabs(baseSeg.cross(p3 - p0)) / (baseSeg.length() * 2);
  return p2 + crossSeg * h1 / (h1 + h2);
}

void solve() {
  Vector2 p = crossPoint();
  if (fabs(p.x) < EPS) cout << 0;
  else cout << p.x;
  cout << ' ';
  if (fabs(p.y) < EPS) cout << 0;
  else cout << p.y;
  cout << endl;
}

void input() {
  cin >> N;
  while (cin >> p0 >> p1 >> p2 >> p3) {
    solve();
  }
}

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

Shun

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!

CGL_2_C Cross Point

# Problem

# Explanation

# Solution

Comments