(20149) 선분 교차 3

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

단계별로 풀어보기

39단계(기하 2) 6번째

 

 

 

선분 교차 2에서 좌표까지 구해야 하는 문제

양 끝점의 좌표를 아는 선분은 함수로 표현할 수 있으므로 연립방정식을 세워 풀면 교점의 좌표를 구할 수 있다.

마찬가지로 네 점의 좌표가 일직선 위에 있을 때가 문제인데, 한 선분의 큰 값의 점이 다른 선분의 작은 값의 점과 일치한다면 그 점이 유일한 교점이고 아니라면 선분이 겹치는 것이므로 생략한다.

 

 

 

#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);
  }
  bool operator ==(const Cord& other) const{
    return make_pair(x,y)==make_pair(other.x,other.y);
  }
};

int main() {
  cout << fixed;
  cout.precision(9);
  
  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){
      if(p2<p1)  swap(p2, p1);
      if(p4<p3)  swap(p4, p3);
      
      if(p1<=p4 && p3<=p2){
        return true;
      }else{
        return false;
      }
    }else if(a<=0&&b<=0){
      return true;
    }else{
      return false;
    }
  };
  
  auto intersection= [](Cord &p1, Cord &p2, Cord &p3, Cord &p4){
    long px= (p1.x*p2.y-p1.y*p2.x)*(p3.x-p4.x)-(p1.x-p2.x)*(p3.x*p4.y-p3.y*p4.x);
    long py= (p1.x*p2.y-p1.y*p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x*p4.y-p3.y*p4.x);
    long pd= (p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x);
    
    if(!pd){
      if(p1==p4)  cout << p1.x << " " << p1.y;
      else if(p2==p3)  cout << p2.x << " " << p2.y;
    }else{
      cout << 1.0*px/pd << " " << 1.0*py/pd;
    }
  };
  
  if(iscross(p[0], p[1], p[2], p[3])){
    cout << "1\n";
    intersection(p[0], p[1], p[2], p[3]);
  }else{
    cout << "0\n";
  }
  
  return 0;
}