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을 찍어 준다.
아 갑자기 이런 경우 판단이 가능하나?? 궁금해졌다. 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);
이제 마지막으로 겹치는 점을 구합니다
끝!