(17387) 선분 교차 2

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

단계별로 풀어보기

39단계(기하 2) 5번째

 

 

 

세 점이 한 직선 위에 있다고 해도 조금만 수정하면 이 교차 판정 알고리즘은 제대로 작동한다.

한 선분과 다른 선분의 양 끝을 ccw로 검사했을 때 0이 있다면 다른 선분은 이 선분을 늘린 직선과 닿는다.

따라서 부호가 반대일 때 말고 0일때도 두 선분은 만난다.

문제는 네 점이 모두 한 직선 위에 있을 때이다. 이때는 각 좌표를 pair처럼 대소를 비교하여 어떤 선분의 양 끝점 사이에 다른 선분의 끝점 중 하나가 있어야 두 선분이 점 또는 선분으로 겹친다는 것이다.

 

 

 

#include <iostream>
using namespace std;

struct Cord{
  long x;
  long y;
  
  Cord(): x(0), y(0) {}
  Cord(long x0, long y0): x(x0), y(y0) {}
  
  bool operator <(const Cord& other) const{
    return make_pair(x,y)<make_pair(other.x,other.y);
  }
  bool operator <=(const Cord& other) const{
    return make_pair(x,y)<=make_pair(other.x,other.y);
  }
};

int main() {
  Cord p[4];
  
  for(int i=0;i<4;i++)  cin >> p[i].x >> p[i].y;
  
  auto ccw= [](Cord &p1, Cord &p2, Cord &p3){
    long t= (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
    
    if(t>0)  return 1;
    else if(t<0)  return -1;
    else  return 0;
  };
  
  auto iscross= [&ccw](Cord &p1, Cord &p2, Cord &p3, Cord &p4){
    long a= ccw(p1,p2,p3)*ccw(p1,p2,p4);
    long b= ccw(p4,p3,p1)*ccw(p4,p3,p2);
    
    if(a==0 && b==0){
      return (min(p1,p2)<=max(p3,p4) && min(p3,p4)<=max(p1,p2));
    }else if(a<=0&&b<=0){
      return true;
    }else{
      return false;
    }
  };
  
  cout << iscross(p[0], p[1], p[2], p[3]);
  
  return 0;
}