문제 링크
두 선분 각각의 양 끝점 좌표를 알려주고, 두 선분이 교차하는지 확인하는 문제이다.
이때 주의할 점은 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는것으로 간주한다는 것이다.
또한 좌표의 범위가 -1,000,000부터 1,000,000까지 이기 때문에 ccw알고리즘 적용시 long long타입으로 좌표를 저장해야 충분하다.
이 문제를 풀때 필요한 알고리즘은 다음과 같다.
1. CCW로 판별하기
P
|
|
R---*------S
|
|
Q
위와 같은 경우 세점을 순서대로 잡았을때 CCW가 어떻게 되는지 살펴보자.
PQS = 반시계
PQR = 시계
RSP = 반시계
RSQ = 시계
이때 PQS != PQR && RSP != RSQ라는 것을 알수 있다. 이는 위의 PQ선분을 왼쪽이나 오른쪽으로 옮겨,
교차점이 R이나 S로 가도 성립함을 알 수 있다. 하지만 그 이상 넘어가면 성립하지 않는다.
이를 통해 둘중 적어도 하나의 선분의 양끝점이 아닌 곳에서 교차하는 경우를 판별할 수 있다.
2. 3점이 일직선인지 판별
1과 달리 아래의 경우들이 있을 수 있다.
P----R---Q----S P----(Q이면서R)----S
이런 경우는 CCW만으로는 판별하기 어렵기 때문에 3점을 잡아
3점이 어느 하나의 선분에 속한것인지 판별하는 알고리즘이 필요하다.
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct Point{
long long x, y;
}Point;
typedef struct Line{
Point p, q;
}Line;
void arrangeLine(Line* line){
Point* p = &(line->p);
Point* q = &(line->q);
if(p->x == q->x){
return;
}
}
/**
* (ry - py)/(rx - px) : (qy - py)/(qx - px)
* : == > - 반시계
*
* @return 1 - 반시계, -1 - 시계, 0 - 일직선
*/
int orientation(Point* p, Point* q, Point* r){
long long val = (r->y - p->y)*(q->x - p->x) - (q->y - p->y)*(r->x - p->x);
if(val > 0) return 1;
if(val < 0) return -1;
return 0;
}
/**
* @brief p와 q사이에 r이 있는가?
*/
bool onSegment(Point* p, Point* q, Point* r){
if(r->x <= max(p->x, q->x) && r->x >= min(p->x, q->x)
&& r->y <= max(p->y, q->y) && r->y >= min(p->y, q->y)) return true;
return false;
}
/**
* @brief
* ccw와 좌표간 겹침을 고려해서 구현해야함.
*
* @param line1
* @param line2
* @return int
*/
int is_intersact(Line line1, Line line2){
int pqr = orientation(&(line1.p), &(line1.q), &(line2.p));
int pqs = orientation(&(line1.p), &(line1.q), &(line2.q));
int rsp = orientation(&(line2.p), &(line2.q), &(line1.p));
int rsq = orientation(&(line2.p), &(line2.q), &(line1.q));
//CCW로 해결 가능한 경우
if(pqr != pqs && rsp != rsq) return true;
//3점의 조합이 평행일때 3개의 점이 둘중 어느 한선분에 속하는것인지 판별
if(pqr == 0 && onSegment(&line1.p, &line1.q, &line2.p)) return true;
if(pqs == 0 && onSegment(&line1.p, &line1.q, &line2.q)) return true;
if(rsp == 0 && onSegment(&line2.p, &line2.q, &line1.p)) return true;
if(rsq == 0 && onSegment(&line2.p, &line2.q, &line1.q)) return true;
return false;
}
int main(){
Line line1, line2;
long long px, py, qx, qy, rx, ry, sx, sy;
cin >> line1.p.x >> line1.p.y >> line1.q.x >> line1.q.y;
cin >> line2.p.x >> line2.p.y >> line2.q.x >> line2.q.y;
cout << is_intersact(line1, line2) << endl;
return 0;
}