์๊ณ ๋ฆฌ์ฆ
-
์ ์ ๋ถ์ด ํํํ ๊ฒฝ์ฐ, ๋๋ ํ ์ชฝ์ด 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();
}