[BOJ/백준] 20149 - 선분 교차 3

20149번: 선분 교차 3

---

CCW

 

+

 

기울기가 무한일 때와 유한일 때

---

---

• 제목

선분 교차 3

---

• 조건

시간 제한 : 0.25 초

메모리 제한 : 512 MB 

---

• 문제

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

---

• 입력

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

---

• 출력

L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다.

두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다.

좌표의 절대/상대 오차는 10-9까지 허용한다

---

• 제한

-1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
x1, y1, x2, y2, x3, y3, x4, y4는 정수
선분의 길이는 0보다 크다.

---

예제 입력1	예제 출력1
1 1 5 5 1 5 5 1	1 3 3

예제 입력2	예제 출력2
1 1 5 5 6 10 10 6	0

예제 입력3	예제 출력3
1 1 5 5 5 5 1 1	1

예제 입력4	예제 출력4
1 1 5 5 3 3 5 5	1

예제 입력5	예제 출력5
1 1 5 5 3 3 1 3	1 3 3

예제 입력6	예제 출력6
1 1 5 5 5 5 9 9	1 5 5

예제 입력7	예제 출력7
1 1 5 5 6 6 9 9	0

예제 입력8	예제 출력8
1 1 5 5 5 5 1 5	1 5 5

예제 입력9	예제 출력9
1 1 5 5 6 6 1 5	0

예제 입력10	예제 출력10
2 8 9 23 1 10 9 8	01 2.7313432835820897 9.5671641791044770

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
#define endl '\n'

#define dot pair<long, long>
#define line pair<dot, dot>

long long ccw(dot a, dot b, dot c){
	long long tmp = (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
	if(tmp > 0) return 1;
	else if(tmp < 0) return -1;
	else return 0;
}

void isMeet(line a, line b){
	bool intersect = false;
	long long ccw1 = ccw(a.first, a.second, b.first);
	long long ccw2 = ccw(a.first, a.second, b.second);
	long long ccw3 = ccw(b.first, b.second, a.first);
	long long ccw4 = ccw(b.first, b.second, a.second);
	
	long long ccwA = ccw1 * ccw2;
	long long ccwB = ccw3 * ccw4;
	if(ccwA <= 0 && ccwB <= 0){
		if(ccwA == 0 && ccwB == 0){
			if(a.first > a.second) swap(a.first, a.second);
			if(b.first > b.second) swap(b.first, b.second);
			intersect = a.first <= b.second && b.first <= a.second;
		}
		intersect = true;
	}
	if(!intersect) cout << 0 << endl;
	else{
		if(ccwA == 0 && ccwB == 0){
			if(ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0){ // same inclination
				if(a.second < b.first || b.second < a.first) cout << 0 << endl;
				else{
					cout << 1 << endl;
					if(a.first == b.second) cout << a.first.first << ' ' << a.first.second << endl;
					if(a.second == b.first) cout << a.second.first << ' ' << a.second.second << endl;
				}
			}
			else{ // one dot + not cross
				if(a.first == b.second || a.first == b.first) {
					cout << 1 << endl;
					cout << a.first.first << ' ' << a.first.second << endl;
				}
				if(a.second == b.first || a.second == b.second) {
					cout << 1 << endl;
					cout << a.second.first << ' ' << a.second.second << endl;
				}
			}
		}
		else{ // different inclination
			cout << 1 << endl;
			long long x1 = a.first.first;
			long long x2 = a.second.first;
			long long y1 = a.first.second;
			long long y2 = a.second.second;
			
			long long x3 = b.first.first;
			long long x4 = b.second.first;
			long long y3 = b.first.second;
			long long y4 = b.second.second;
			
			double x = (x1 * y2 - y1 * x2) * (x3 - x4)  - (x1 - x2) * (x3 * y4 - y3 * x4);
			x /= (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
			
			double y = (x1 * y2 - y1 * x2) * (y3 - y4)  - (y1 - y2) * (x3 * y4 - y3 * x4);
			y /= (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
			
			cout << x << ' ' << y << endl;
		}
	}
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    	
	cout << fixed;
	cout.precision(9);
	long long x1, x2, y1, y2;
	line l[2];
	for(int n = 0 ; n < 2 ; n++){
		cin >> x1 >> y1 >> x2 >> y2;
		l[n] = {{x1, y1}, {x2, y2}};
	}
	isMeet(l[0], l[1]);
    return 0;
}