선분 교차 판별법

오늘 어이없게 시간 날려서 박제용으로 포스트

/* 인수를 넘겨 받을 때 int를 사용하게 되면 중간 계산 결과가 overflow 발생한다 */
int cross(pair<long double,long double> v1,pair<long double,long double> v2){
   long double ans=v1.first*v2.second-v1.second*v2.first;
   if(ans>0) return 1;
   else if(ans==0) return 0;
   else return -1;
}
/*주의 : 일직선상에 놓이면 a*b==0 && c*d==0이지만 역은 성립 안한다. 이걸 놓쳤다.*/
/* 세 점이 일직선상에 놓이게 되면 a*b==0 && c*d==0  따라서 4점이 일직선상에 놓이게 되는
경우에도 위 사례가 성립하지만 4점이 일직선상에 놓인다고 해서 둘다 0이 되진 않는다.*/
if(a*b==0 && c*d==0){
   if(input2<input3||input4<input1) cout<<0<<endl;
   else {
      cout<<1<<endl;
	  if(a==0&&b==0&&c==0&&d==0){ //일직선상에 위치할 때 (정렬끝)
	  if(input1==input3||input2==input4) ans=2;  //시작점끼리 같거나 끝점끼리 같은경우
	  else if(input1<input3&&input4<input2) ans=2;
	  else if(input3<input1&&input2<input4) ans=2;
	  else ans=1;
   }			
}

생각보다 놓칠 수 있는 경우라서 조심해야겠다.

예전에 2-SAT풀면서 operator를 사용했던 기억이 있는데 pair의 비교를 사용하면 굳이 필요가 없었다.