[C++] 백준 17387 - 선분 교차 2(ccw, 계산기하)

0. [c++] 백준  -

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

1. 풀이

선분 교차 1이랑 비슷해유

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190

#include<iostream> #include<vector> #include<algorithm> #include<math.h>     using namespace std;   const double PI = 2.0 * acos(0.0); const double EPSILON = 1e-9;   struct vector2 {     double x, y;     explicit vector2(double x_, double y_) :x(x_), y(y_) {}     bool operator == (const vector2& rhs) const {         return (x == rhs.x && y == rhs.y);     }     bool operator < (const vector2& rhs) const {         return (x != rhs.x ? x < rhs.x : y < rhs.y);     }     vector2 operator + (const vector2& rhs) const {         return vector2(x + rhs.x, y + rhs.y);     }     vector2 operator - (const vector2& rhs) const {         return vector2(x - rhs.x, y - rhs.y);     }     vector2 operator * (double rhs) const {         return vector2(x * rhs, y * rhs);     }       //벡터의 길이를 반환한다.     double norm() const { return hypot(x, y); }     //방향이 같은 단위 벡터를 반환한다.     vector2 normalize() const {         return vector2(x / norm(), y / norm());     }     //x축의 양의 방향으로부터 이 벡터까지의 반시계방향으로 잰 각도     double polar() const { return fmod(atan2(y, x) + 2 * PI, 2 * PI); }     //내적,외적의 구현     double dot(const vector2& rhs) const {         return  x * rhs.x + y * rhs.y;     }     double cross(const vector2& rhs) const {         return x * rhs.y - y * rhs.x;     }     //이 벡터를 rhs에 사영한 결과     vector2 project(const vector2& rhs) const {         vector2 r = rhs.normalize();         return r * r.dot(*this);     }   };   //++문제에 따라 추가해야 할 함수   //double형의 실수형 오류 방지 bool relativeEqual(double a, double b) {     double diff = fabs(a - b);     if (diff < 1e-10)return true;     return diff <= 1e-8 * max(fabs(a), fabs(b)); }   //두 벡터의 사이각(세타) double Interval(vector2 a, vector2 b) {     return acos(a.dot(b) / a.norm() * b.norm()); }   //단순 다각형 p의 넓이를 구한다. double area(const vector<vector2>& p) {     double ret = 0;     for (int i = 0; i < p.size(); i++)     {         int j = (i + 1) % p.size();         ret += p[i].x * p[j].y - p[j].x * p[i].y;     }     return fabs(ret) / 2.0; }   //3개의 점에서 a가 b보다 얼마나 p에 가까운지 반환하는 함수 double howMuchCloser(vector2 p, vector2 a, vector2 b) {     return (b - p).norm() - (a - p).norm(); }   //위의 과정을 2개의 실수를 활용해 표현하는 방법 double howMuchCloser22(double px, double py, double ax, double ay, double bx, double by) {     return sqrt((bx - px) * (bx - px) + (by - py) * (by - py)) - sqrt((ax - px) * (ax - px) + (ay - py) * (ay - py)); }       //코드 15.2 두 벡터의 방향성을 판단하는 ccw() 함수의 구현   //원점에서 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수, //평행이면 0을 반환한다. double ccw(vector2 a, vector2 b) {     return a.cross(b); }   //점 p를 기준으로 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수, //평행이면 0을 반환한다. double ccw(vector2 p, vector2 a, vector2 b) {     return ccw(a - p, b - p); }         //코드 15.3 두 직선의 교차점을 계산하는 linelntersection() 함수의 구현   //(a,b)를 포함하는 선과 (c,d)를 포함하는 선의 교점을 x에 반환한다. //두 선이 평행이면 (겹치는 경우를 포함) 거짓을, 아니면 참을 반환한다. bool lineIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& x) {     double det = (b - a).cross(d - c);     //두 선이 평행인 경우     if (fabs(det) < EPSILON) return false;     x = a + (b - a) * ((c - a).cross(d - c) / det);     return true; }       //코드 15.4 선분과 선분의 교차점을 계산하는 segmentlntersection()의 구현   //(a,b)와 (c,d)가 평행한 두 선분일 때 이들이 한 점에서 겹치는지 확인한다. bool parallelSegments(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p) {     if (b < a) swap(a, b);     if (d < c) swap(c, d);     //한 직선 위에 없거나 두 선분이 겹치지 않는 경우를 우선 걸러낸다.     if (ccw(a, b, c) != 0 || b < c || d < a) return false;     //두 선분은 확실히 겹친다. 교차점을 하나 찾자.     if (a < c) p = c; else p = a;     return true; } //p가 (a,b)를 감싸면서 각 변이 x,y 축에 평행한 최소 사각형 내부에 있는지 확인한다. //a,b,p는 일직선 상에 있다고 가정한다. bool inBoundingRectangle(vector2 p, vector2 a, vector2 b) {     if (b < a) swap(a, b);     return p == a || p == b || (p < a&& p < b); } //(a,b) 선분과 (c,d) 선분의 교점을 p에 반환한다. //교점이 여러 개일 경우 아무 점이나 반환한다. //두 선분이 교차하지 않을 경우 false를 반환한다. bool segmentIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p) {     //두 직선이 평행인 경우를 우선 예외로 처리한다.     if (!lineIntersection(a, b, c, d, p))         return parallelSegments(a, b, c, d, p);     //p가 두 선분에 포함되어 있는 경우에만 참을 반환한다.     return inBoundingRectangle(p, a, b) && inBoundingRectangle(p, c, d); }         //15.5 두 선분의 교차 여부를 좀더 간단하게 확인하는 segmentIntersects() 함수의 구현   //두 선분이 서로 접촉하는지 여부를 반환한다. bool segmentsIntersectects(vector2 a, vector2 b, vector2 c, vector2 d) {     double ab = ccw(a, b, c) * ccw(a, b, d);     double cd = ccw(c, d, a) * ccw(c, d, b);     //두 선분이 한 직선 위에 있거나 끝점이 겹치는 경우     if (ab == 0 && cd == 0) {         if (b < a) swap(a, b);         if (d < c) swap(c, d);         return !(b < c || d < a);     }     return ab <= 0 && cd <= 0; }   int main() {       double x, y;     cin >> x >> y;     vector2 a(x, y);     cin >> x >> y;     vector2 b(x, y);     cin >> x >> y;     vector2 c(x, y);     cin >> x >> y;     vector2 d(x, y);       vector2 xx(x, y);       if (segmentsIntersectects(a, b,c,d))         cout << 1;     else         cout << 0;       return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!