BOJ 17387 선분 교차2

https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

 

 

CCW를 이용하면 쉽게 풀수 있는 문제다.

하지만, 나는 의외의 곳에서 내 코드의 반례를 찾지 못했다.
아래는 내가 처음 작성한 코드이다.

#include <algorithm>
#include <cstdio>

typedef long long ll;

using namespace std;

int ccw(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){
	ll t = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1);
	if(t>0) return 1;
	else if(t==0) return 0;
	else return -1;
}

int main() {
	int x1,x2,x3,x4, y1,y2,y3,y4;
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	scanf("%d%d%d%d",&x3,&y3,&x4,&y4);
	
	int a = ccw(x1,y1,x3,y3,x2,y2)*ccw(x1,y1,x4,y4,x2,y2);
	int b = ccw(x3,y3,x1,y1,x4,y4)*ccw(x3,y3,x2,y2,x4,y4);
	
	printf("%d %d\n",a,b);
	if(a <= 0 && b <= 0){
		if(a == 0 && b == 0){
            //문제인 부분
			if((min(x1,x2) <= max(x3,x4)) &&
			   (min(x3,x4) <= max(x1,x2)))
				printf("1\n");
			else printf("0\n");
		}
		else printf("1\n");
	} 
	else printf("0\n");
	return 0;
}

 

이 코드의 문제점은 x = n 직선 위에 두 선분이 존재할 경우, 제대로 교차 확인이 불가능하다는 문제가 있었다.
사실 이 문제점은 다른 분들의 코드를 참고해서 알게 되었다.
(참고 코드 : https://hsdevelopment.tistory.com/390)

최종 코드는 다음과 같다.

#include <algorithm>
#include <cstdio>
#include <cassert>

typedef long long ll;

using namespace std;

int ccw(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){
	ll t = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1);
	if(t>0) return 1;
	else if(t==0) return 0;
	else return -1;
}

bool solve(){
	ll x1,x2,x3,x4, y1,y2,y3,y4;
	scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
	scanf("%lld%lld%lld%lld",&x3,&y3,&x4,&y4);
	
	int a = ccw(x1,y1,x3,y3,x2,y2)*ccw(x1,y1,x4,y4,x2,y2);
	int b = ccw(x3,y3,x1,y1,x4,y4)*ccw(x3,y3,x2,y2,x4,y4);
	
	if(a == 0 && b == 0){
        pair<ll, ll> p1 = {x1, y1};
        pair<ll, ll> p2 = {x2, y2};
        pair<ll, ll> p3 = {x3, y3};
        pair<ll, ll> p4 = {x4, y4};
        
		if(p1 > p2) swap(p1, p2);
		if(p3 > p4) swap(p3, p4);
        
		return p1 <= p4 && p3 <= p2;
	}
	return a <= 0 && b <= 0;
}

int main() {
	printf("%d\n",solve());
}