์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ์–‘ ์„ ๋ถ„์ด ํ‰ํ–‰ํ•  ๊ฒฝ์šฐ, ๋˜๋Š” ํ•œ ์ชฝ์ด x์ถ•์— ํ‰ํ–‰ํ•˜๊ณ , ๋‹ค๋ฅธ ์ถ•์ด y์ถ•์— ํ‰ํ–‰ํ•  ๊ฒฝ์šฐ์—” ์กฐ๊ฑด๋ฌธ์„ ํ†ตํ•ด ๋ฒ”์œ„๋ฅผ ์ž˜ ๊ฒ€์‚ฌํ•˜์—ฌ ์ฒ˜๋ฆฌ

  • ๋‚˜๋จธ์ง€ ๊ฒฝ์šฐ์—” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•œ๋‹ค.

    • ์ฒซ๋ฒˆ์งธ ์„ ๋ถ„์„ ์ด๋ฃจ๋Š” ์ง์„ ์ด ๋‘๋ฒˆ์งธ ์„ ๋ถ„์„ ์–‘๋ถ„ํ•˜๊ณ , ๊ทธ ๋ฐ˜๋Œ€๋„ ์–‘๋ถ„ํ•˜๋ฉด ๋‘ ์„ ๋ถ„์€ ๊ต์ฐจํ•œ๋‹ค.

    • ์ด๋•Œ ํ•œ ์ง์„ ์ด ํ•œ ์„ ๋ถ„์„ ์–‘๋ถ„ํ•˜๋Š”์ง€ ์•Œ์•„๋ณด๋Š” ์‹์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

      f1 = (y21-y11)(x12-x11) - (x21-x11)(y12-y11)

      f2 = (y22-y11)(x12-x11) - (x22-x11)(y12-y11)

      ์ด๊ณ , f1 * f2 < 0 ์ผ๋•Œ ์–‘๋ถ„ํ•จ.

    • ์ด๋•Œ, ์ด ๋ฌธ์ œ์—์„œ๋Š” ๋ ์ ์— ์ง€๋‚˜๋Š” ๊ฒƒ๋„ ๊ต์ฐจํ•œ๋‹ค๊ณ  ํŒ๋‹จํ•˜๋‹ˆ, f1 * f2 โ‡ 0 ์ผ๋•Œ ์ฐธ์œผ๋กœ ํŒ๋‹จํ•˜์ž.

      ๋‹จ, ์ด๋Ÿฌ๋ฉด ํ‰ํ–‰ํ• ๋•Œ๋„ 0์ด ๋‚˜์˜ค๋‹ˆ, ํ‰ํ–‰ ๊ฒ€์‚ฌ๋Š” ์ด ๋ฐฉ๋ฒ•๋ณด๋‹ค ๋จผ์ € ํ•˜์ž.

์ฝ”๋“œ

#include <iostream>
typedef long long ll;
using namespace std;
 
struct line {
	ll h, t, ch, ct;
};
 
void swap(ll* a, ll* b) {
	ll t = *a;
	*a = *b;
	*b = t;
}
void makeLine(line* l, ll x1, ll x2, ll y1, ll y2) {
	ll b = x2 - x1, h = y2 - y1;
	if (b < 0 && h < 0) {
		b *= -1;
		h *= -1;
	}
 
	ll ch = b * y1 - h * x1, ct = b;
	*l = { h, b, ch, ct };
}
 
bool check(ll x1, ll x2, ll x3, ll y1, ll y2, ll y3) {
	if ((((x3 >= x1 && x3 <= x2) && (y3 >= y1 && y3 <= y2))|| ((x3 <= x1 && x3 >= x2) && (y3 <= y1 && y3 >= y2))))
		return true;
	return false;
}
 
bool is_cross(ll x1, ll x2, ll x3, ll x4, ll y1, ll y2, ll y3, ll y4) {
	ll f1 = ((y3 - y1) * (x2 - x1)) - ((x3 - x1) * (y2 - y1)), f2 = ((y4 - y1) * (x2 - x1)) - ((x4 - x1) * (y2 - y1));
	if ((f1 <= 0 && f2 >= 0) || (f1 >= 0 && f2 <= 0))
		return true;
	return false;
}
 
bool solve() {
	ll x1, x2, x3, x4, y1, y2, y3, y4;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
 
	if (x1 > x2) {
		swap(&x1, &x2);
		swap(&y1, &y2);
	}
	if (x3 > x4) {
		swap(&x3, &x4);
		swap(&y3, &y4);
	}
 
	line l1, l2;
	makeLine(&l1, x1, x2, y1, y2);
	makeLine(&l2, x3, x4, y3, y4);
 
	if (l1.h * l2.t == l1.t * l2.h) {
		if (l1.ch * l2.ct == l1.ct * l2.ch && (check(x1, x2, x3, y1, y2, y3) || check(x1, x2, x4, y1, y2, y4) || check(x3, x4, x1, y3, y4, y1) || check(x3, x4, x2, y3, y4, y2)))
			return 1;
		return 0;
	}
	else if (l1.t == 0 && l2.h == 0) {
		if (x1 >= x3 && x1 <= x4 && ((y3 >= y1 && y3 <= y2) || (y3 <= y1 && y3 >= y2)))
			return 1;
		return 0;
	}
	else if (l2.t == 0 && l1.h == 0) {
		if (x3 >= x1 && x3 <= x2 && ((y1 >= y3 && y1 <= y4) || (y1 <= y3 && y1 >= y4)))
			return 1;
		return 0;
	}
 
	if (is_cross(x1, x2, x3, x4, y1, y2, y3, y4) && is_cross(x3, x4, x1, x2, y3, y4, y1, y2))
		return 1;
	return 0;
}
 
int main() {
	cout << solve();
}