test/AOJCGL-2B.test.cpp

View this file on GitHub
Last update: 2023-03-08 21:36:18+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/2/CGL_2_B

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/2/CGL_2_B"

#include "../src/geometryR2/segment.hpp"
#include "../src/geometryR2/relation.hpp"

#include <iostream>

int main() {
	using namespace geoR2;
	int q; std::cin >> q;
	for (int _ = 0 ; _ < q ; _++) {
		segment s1, s2;
		std::cin >> s1.e1 >> s1.e2 >> s2.e1 >> s2.e2;
		std::cout << isIntersect(s1, s2) << std::endl;
	}
}

#line 1 "test/AOJCGL-2B.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/2/CGL_2_B"

#line 2 "src/geometryR2/segment.hpp"

#line 2 "src/geometryR2/ccw.hpp"

#line 2 "src/geometryR2/point.hpp"

#line 2 "src/geometryR2/base.hpp"

#include <cmath>

namespace geoR2 {

using real = long double;

const real PI = acosl(-1);

inline real &eps() {
	static real EPS = 1e-14;
	return EPS;
}

inline void setEps(const real& EPS = 1e-14) {
	eps() = EPS;
}

inline int sgn(const real& value) {
	return (value < -eps() ? -1 : (value > +eps() ? 1 : 0));
}

inline bool equals(const real& a, const real& b) {
	return sgn(a - b) == 0;
}

inline real toRadian(const real& value) {
	return (value * PI) / 180;
}

} // namespace geoR2

namespace literals {

geoR2::real operator"" _rad(unsigned long long value) {
	return (static_cast<geoR2::real>(value) * geoR2::PI) / static_cast<geoR2::real>(180);
}

} // namespace literals

using namespace literals;
#line 4 "src/geometryR2/point.hpp"

#line 6 "src/geometryR2/point.hpp"
#include <istream>
#include <ostream>

namespace geoR2 {

struct point {
	real x, y;
	
	point() : x(0), y(0) {}
	point(const real& _x, const real& _y) : x(_x), y(_y) {}

	friend std::ostream &operator <<(std::ostream& os, const point& p) {
		return os << p.x << ' ' << p.y;
	}
	friend std::istream &operator >>(std::istream& is, point& p) {
		is >> p.x >> p.y;
		return is;
	}
	
	point &operator +=(const point& p) {
		x += p.x; y += p.y;
		return *this;
	}
	point &operator -=(const point& p) {
		x -= p.x; y -= p.y;
		return *this;
	}
	point &operator *=(const real& k) {
		x *= k; y *= k;
		return *this;
	}
	point &operator /=(const real& k) {
		x /= k; y /= k;
		return *this;
	}

	point operator +(const point& p) const {
		return point(*this) += p;	
	}
	point operator -(const point& p) const {
		return point(*this) -= p;
	}
	point operator *(const real& k) const {
		return point(*this) *= k;
	}
	friend point operator *(const real& r, const point& p) {
		return point(p) *= r;
	}
	point operator /(const real& k) const {
		return point(*this) /= k;
	}
	point operator +() const {
		return point(*this);
	}
	point operator -() const {
		return point(-x, -y);
	}

	real squareDistance() const {
		return x * x + y * y;
	}

	real distance() const {
		return sqrtl(x * x + y + y);
	}

	point rotated(const real& theta) const {
		return point(x * cosl(theta) - y * sinl(theta), x * sinl(theta) + y * cosl(theta));
	}
};

real dot(const point& a, const point& b) {
	return a.x * b.x + a.y * b.y;
}

real cross(const point& a, const point& b) {
	return a.x * b.y - a.y * b.x;
}

bool equals(const point& a, const point& b) {
	return equals(a.x, b.x) and equals(a.y, b.y);
}

using vec2 = point;

} // namespace geoR2
#line 2 "src/geometryR2/line.hpp"

#line 4 "src/geometryR2/line.hpp"

#include <cassert>

namespace geoR2 {

struct line {
	point a, b;

	line() : a(0, 0), b(0, 0) {}
	line(const point& _a, const point& _b) : a(_a), b(_b) {}

	inline bool isValid() const {
		return !equals(a, b);
	}

};

} // namespace geo2d
#line 6 "src/geometryR2/ccw.hpp"

namespace geoR2 {

enum class CCW {
	COUNTER_CLOCKWISE,
	CLOCKWISE,
	ONLINE_BACK,
	ONLINE_FRONT,
	ON_SEGMENT,
};

CCW ccw(const vec2& a, const vec2& b) {
	int outer = sgn(cross(a, b));
	if (outer == 1) {
		return CCW::COUNTER_CLOCKWISE;
	}
	else if (outer == -1) {
		return CCW::CLOCKWISE;
	}
	else if (sgn(dot(a, b)) == -1) {
		return CCW::ONLINE_BACK;
	}
	else if (a.squareDistance() < b.squareDistance()) {
		return CCW::ONLINE_FRONT;
	}
	else {
		return CCW::ON_SEGMENT;
	}
}

} // namespace geoR2
#line 5 "src/geometryR2/segment.hpp"

namespace geoR2 {

struct segment {

	point e1, e2;

	segment() : e1(), e2() {}
	segment(const point& _e1, const point& _e2) : e1(_e1), e2(_e2) {}

	bool isValid() const {
		return !equals(e1, e2);
	}
};

} // namespace R2
#line 2 "src/geometryR2/relation.hpp"

#line 7 "src/geometryR2/relation.hpp"

namespace geoR2 {
namespace impl {

int _ccw(const vec2& a, const vec2& b) {
	CCW value = ccw(a, b);
	if (value == CCW::COUNTER_CLOCKWISE) {
		return 1;
	}
	else if (value == CCW::CLOCKWISE) {
		return -1;
	}
	else if (value == CCW::ON_SEGMENT) {
		return 0;
	}
	else if (value == CCW::ONLINE_BACK) {
		return 2;
	}
	else {
		return -2;
	}
}

} // namespace impl

bool isOrthogonal(const line& l1, const line& l2) {
	assert(l1.isValid());
	assert(l2.isValid());
	return sgn(dot(l1.b - l1.a, l2.b - l2.a)) == 0;
}

bool isParallel(const line& l1, const line& l2) {
	assert(l1.isValid());
	assert(l2.isValid());
	return sgn(cross(l1.b - l1.a, l2.b - l2.a)) == 0;
}

bool isIntersect(const segment& s1, const segment& s2) {
	assert(s1.isValid());
	assert(s2.isValid());
	vec2 v1(s1.e2 - s1.e1), v2(s2.e2 - s2.e1);
	return 
		impl::_ccw(v1, s2.e1 - s1.e1) * impl::_ccw(v1, s2.e2 - s1.e1) <= 0 
		and
		impl::_ccw(v2, s1.e1 - s2.e1) * impl::_ccw(v2, s1.e2 - s2.e1) <= 0;
}

} // namespace geoR2
#line 5 "test/AOJCGL-2B.test.cpp"

#include <iostream>

int main() {
	using namespace geoR2;
	int q; std::cin >> q;
	for (int _ = 0 ; _ < q ; _++) {
		segment s1, s2;
		std::cin >> s1.e1 >> s1.e2 >> s2.e1 >> s2.e2;
		std::cout << isIntersect(s1, s2) << std::endl;
	}
}