20149 선분 교차 3

으으으 구현 열심히 했는데 실수가 있었는지 틀렸다.

누더기 된 코드 확인하는 것보다 멀끔한 북님 코드 분석하는게 더 좋을 것 같아서 개쓰래기 코드를 들고 오지는 않겠다. 

 

아래는 북님 코드 전문이고 이제 분석도 해보자

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

i64 ccw(i64 x1, i64 y1, i64 x2, i64 y2, i64 x3, i64 y3)
{
	i64 cross = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);

	if (cross > 0)
		return 1;

	if (cross < 0)
		return -1;

	return 0;
}

bool intersect(i64 x1, i64 y1, i64 x2, i64 y2, i64 x3, i64 y3, i64 x4, i64 y4)
{
	int l1l2 = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4);
	int l2l1 = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);

	if (l1l2 == 0 && l2l1 == 0)
	{
		if (ii64(x2, y2) < ii64(x1, y1))
		{
			swap(x1, x2);
			swap(y1, y2);
		}

		if (ii64(x4, y4) < ii64(x3, y3))
		{
			swap(x3, x4);
			swap(y3, y4);
		}

		return ii64(x3, y3) <= ii64(x2, y2) && ii64(x1, y1) <= ii64(x4, y4);
	}

	return l1l2 <= 0 && l2l1 <= 0;
}

i64 gcd(i64 a, i64 b)
{
	if (b == 0)
		return a;

	return gcd(b, a % b);
}

int main()
{
	i64 x1, y1, x2, y2, x3, y3, x4, y4;
	scanf("%lld %lld %lld %lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);

	if (!intersect(x1, y1, x2, y2, x3, y3, x4, y4))
	{
		printf("0\n");
		return 0;
	}

	printf("1\n");

	i64 dx1 = x1 - x2, dy1 = y1 - y2;
	i64 dx2 = x3 - x4, dy2 = y3 - y4;

	i64 g1 = gcd(dx1, dy1);
	dx1 /= g1;
	dy1 /= g1;

	
	i64 g2 = gcd(dx2, dy2);
	dx2 /= g2;
	dy2 /= g2;

	if (dx1 == dx2 && dy1 == dy2)
	{
		i64 x = min(max(x1, x2), max(x3, x4)) - max(min(x1, x2), min(x3, x4));
		i64 y = min(max(y1, y2), max(y3, y4)) - max(min(y1, y2), min(y3, y4));

		if (x > 0 || y > 0)
			return 0;

		if ((x1 == x3 && y1 == y3) || (x1 == x4 && y1 == x4))
			printf("%lld %lld\n", x1, y1);
		else
			printf("%lld %lld\n", x2, y2);

		return 0;
	}

	i64 pxu = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4);
	i64 pxd = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
	i64 pyu = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4);
	i64 pyd = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);

	double px = (double)pxu / pxd;
	double py = (double)pyu / pyd;

	printf("%.12lf %.12lf", px, py);

	return 0;
}

 

선분 교차를 확인하는데 CCW 알고리즘이 쓰였다. CCW는 두 점의 방향성을 나타내는 알고리즘인데 이걸 사용해서 두 점이 교차하는지 알 수 있다.

 

구분할 수 있는 경우는 

- 반시계 방향인 경우

- 시계 방향인 경우

- 세 점이 평행한 경우 

 

공식은 (x2 -x1) * (y3 - y1) - (y2 - y1)(x3 - x1) 으로 판별 가능하다. 결과가 0보다 작으면 시계 방향, 결과가 0보다 크면 반시계 방향, 0이면 평행하다. 

 

CCW(A,B,C)*CCW(A,B,D)<=0 이면서 CCW(C,D,A)*CCW(C,D,B)<=0 이면 두 점이 교차하는지 확인할 수 있다. 

참고

https://jason9319.tistory.com/358

 

그리고 두 직선이 일직선이라면 겹칠 수도 있고 안 겹칠 수도 있어서 이 때는 범위를 확인해주면 된다.

 

이걸 알아야 깔끔히 풀 수 있구나!

 

---

 

아래는 조각조각 확인해보기

 

i64 ccw(i64 x1, i64 y1, i64 x2, i64 y2, i64 x3, i64 y3)
{
	i64 cross = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);

	if (cross > 0)
		return 1;

	if (cross < 0)
		return -1;

	return 0;
}

 

CCW 알고리즘이다 (끄덕)

 

bool intersect(i64 x1, i64 y1, i64 x2, i64 y2, i64 x3, i64 y3, i64 x4, i64 y4)
{
	int l1l2 = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4);
	int l2l1 = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);

	if (l1l2 == 0 && l2l1 == 0)
	{
		if (ii64(x2, y2) < ii64(x1, y1))
		{
			swap(x1, x2);
			swap(y1, y2);
		}

		if (ii64(x4, y4) < ii64(x3, y3))
		{
			swap(x3, x4);
			swap(y3, y4);
		}

		return ii64(x3, y3) <= ii64(x2, y2) && ii64(x1, y1) <= ii64(x4, y4);
	}

	return l1l2 <= 0 && l2l1 <= 0;
}

 

이건 겹치는지 확인하는 함수이다.

선분 두 개를 비교해서 CCW 결과를 파악한다. 

 

l1l2 <= 0 && l2l1 <= 0; 이게 겹치는 건지 파악하는 부분이다. 둘다 0인 경우는 평행한 경우인데 이 때는 좌표를 비교해서 겹치는지 확인한다. 

 

	printf("1\n");

 

이제 점을 열심히 구해보자. 이까지 온 거면 겹치긴 한다는 거니깐 1을 찍어 준다.

 

https://jason9319.tistory.com/358

아 갑자기 이런 경우 판단이 가능하나?? 궁금해졌다. AB를 기준으로 C랑 D의 방향을 구해보면 방향이 같다!!! 여기서 판단이 가능하구나. 개념 이해가 부족했다. 

 

그럼 다시 코드를 보자

 

	i64 dx1 = x1 - x2, dy1 = y1 - y2;
	i64 dx2 = x3 - x4, dy2 = y3 - y4;

	i64 g1 = gcd(dx1, dy1);
	dx1 /= g1;
	dy1 /= g1;

	
	i64 g2 = gcd(dx2, dy2);
	dx2 /= g2;
	dy2 /= g2;

 

기울기를 구하자

(y2 - y1) / (x2 - x1) 이니 dx, dy를 미리 구하자. 

 

if (dx1 == dx2 && dy1 == dy2)
	{
		i64 x = min(max(x1, x2), max(x3, x4)) - max(min(x1, x2), min(x3, x4));
		i64 y = min(max(y1, y2), max(y3, y4)) - max(min(y1, y2), min(y3, y4));

		if (x > 0 || y > 0)
			return 0;

		if ((x1 == x3 && y1 == y3) || (x1 == x4 && y1 == x4))
			printf("%lld %lld\n", x1, y1);
		else
			printf("%lld %lld\n", x2, y2);

		return 0;
	}

 

이제 기울기가 같은 경우를 확인한다. 

 

		i64 x = min(max(x1, x2), max(x3, x4)) - max(min(x1, x2), min(x3, x4));
		i64 y = min(max(y1, y2), max(y3, y4)) - max(min(y1, y2), min(y3, y4));

		if (x > 0 || y > 0)
			return 0;

이건 뭐지...? 일단 양수인 경우 바로 return 하니 완전 일치하는 경우를 판단하는 것 같다. 

 

x1, y1 = 1, 1 / x2, y2 = 5, 5 / x3, y3 = 2, 2 / x4, y4 = 6, 6 인 경우

 

min(5, 6) // 뒤에 좌표 중 작은 거

max(1, 2) //앞에 좌표 중 큰 거

아 이해갔다. 겹치는 부분 있는지 확인하는 거구나! 패스패스

 

뒤에 있는 것들은 일직선인데 한 점이 겹치는 경우 체크한 거고

 

	i64 pxu = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4);
	i64 pxd = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
	i64 pyu = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4);
	i64 pyd = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);

	double px = (double)pxu / pxd;
	double py = (double)pyu / pyd;

	printf("%.12lf %.12lf", px, py);

 

이제 마지막으로 겹치는 점을 구합니다

끝!