[백준 17386] 선분 교차 1

문제 링크 => 17386번: 선분 교차 1 (acmicpc.net)

17386번: 선분 교차 1

---

CCW 를 이용하여 해결하는 문제이다.

 

CCW 를 이용하는 문제 링크 => [백준 11758] CCW :: M - J - C (tistory.com) 를 참고하면 좋을듯 하다.

 

세 점이 일직선 위에 있는 경우가 없으므로 다음을 만족하는지를 판단하면 끝이다.

 

CCW(A, B, C) * CCW(A, B, D) < 0 이면서 CCW(C, D, A) * CCW(C, D, B) < 0 이여야 한다.

 

좌표 값이 1,000,000 임을 유의하여 CCW 값을 단순한 외적 값을 return 하지 않고 양수인 경우 1, 음수인 경우 -1, 0인 경우 0 을 return 해야 overflow 가 발생하지 않도록 주의해야 한다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

ll x_1, x_2, x_3, x_4;
ll y_1, y_2, y_3, y_4;
pair<ll, ll> v1, v2, v3;

void input() {
	cin >> x_1 >> y_1 >> x_2 >> y_2;
	cin >> x_3 >> y_3 >> x_4 >> y_4;
}

ll getCross(pair<ll, ll> x, pair<ll, ll> y) {
	ll ret = x.first * y.second - x.second * y.first;
	if (ret > 0) return 1;
	else if (ret == 0) return 0;
	else return -1;
}

void solve() {
	v1.first = x_2 - x_1, v1.second = y_2 - y_1;
	v2.first = x_3 - x_1, v2.second = y_3 - y_1;
	v3.first = x_4 - x_1, v3.second = y_4 - y_1;
	ll CCW1 = getCross(v1, v2) * getCross(v1, v3);

	v1.first = x_4 - x_3, v1.second = y_4 - y_3;
	v2.first = x_1 - x_3, v2.second = y_1 - y_3;
	v3.first = x_2 - x_3, v3.second = y_2 - y_3;
	ll CCW2= getCross(v1, v2) * getCross(v1, v3);
	
	if (CCW1 < 0 && CCW2 < 0) cout << 1;
	else cout << 0;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();

	return 0;
}