(17386) 선분 교차 1

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

단계별로 풀어보기

39단계(기하 2) 4번째

 

 

 

한 선분의 양 끝점과 다른 선분의 끝점 각각을 ccw 알고리즘으로 검사했을 때 부호가 반대라면 다른 선분은 이 선분을 늘린 직선의 서로 다른 영역에 존재한다. 두 선분 각각이 이를 만족한다면 두 선분은 겹친다.

단 이 방식은 어떤 세 점도 같은 직선 상에 있지 않을 때(ccw가 0인 경우가 없을 때)만 성립한다.

 

 

 

#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) {}
};

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;
  };
  
  cout << (ccw(p[0],p[1],p[2])*ccw(p[0],p[1],p[3])<0
          && ccw(p[3],p[2],p[0])*ccw(p[3],p[2],p[1])<0);
  
  return 0;
}