Algorithm - 선분 교차 판별

개념

CCW 알고리즘을 사용하여 판별할 수 있다.

 

선분 교차 1

위 케이스 같은 경우 CCW(C, D, B) * CCW(C, D, A) 가 음수인 경우 선분이 교차한다고 할 수 있다.

 

선분 교차 1 반례

하지만 위 그림과 같은 경우가 있을 수도 있다.

이러한 경우 CCW(C, D, B) * CCW(C, D, A) < 0 &&  CCW(A, B, C) * CCW(A, B, D) < 0 으로 확인하여 찾을 수 있다.

선분 교차 2

 

위 케이스 같은 경우 CCW(A, B, C) == 0 && CCW(A, B, D) == 0을 만족하고 C가 A와 B 사이에 있는지 확인하면 된다.

---

작동원리

1. CCW로 판별한다.

---

시간복잡도

CCW를 사용할 때 O(1)

---

문제

2162 선분 그룹

www.acmicpc.net/problem/2162

2162번: 선분 그룹

---

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Point {
public:
    long long x, y;

    Point() {

    }

    Point(long long x, long long y) : x(x), y(y) {

    }

    const bool operator<(const Point &other) const {
        if(x != other.x) {
            return x < other.x;
        }

        return y < other.y;
    }

    const bool operator==(const Point &other) const {
        return x == other.x && y == other.y;
    }

    const bool operator<=(const Point &other) const {
        return operator<(other) || operator==(other);
    }
};

class Edge {
public:
    Point p1, p2;

    Edge() {

    }

    Edge(Point p1, Point p2) : p1(p1), p2(p2) {

    }
};

long long ccw(Point p1, Point p2, Point p3) {
    long long left = p1.x*p2.y + p2.x*p3.y + p3.x*p1.y;
    long long right = p2.x*p1.y + p3.x*p2.y + p1.x*p3.y;

    return left - right;
}

bool isCross(Edge e1, Edge e2) {
    long long left = ccw(e1.p1, e1.p2, e2.p1) * ccw(e1.p1, e1.p2, e2.p2);
    long long right = ccw(e2.p1, e2.p2, e1.p1) * ccw(e2.p1, e2.p2, e1.p2);

    if(left == 0 && right == 0) {
        if(e1.p2 < e1.p1) {
            swap(e1.p1, e1.p2);
        }

        if(e2.p2 < e2.p1) {
            swap(e2.p1, e2.p2);
        }

        if(e2.p1 < e1.p1) {
            swap(e1, e2);
        }

        return e2.p1 <= e1.p2;
    }

    return left <= 0 && right <= 0;
}

int n;
vector<Edge> ve;

vector<int> disjoint;
int func(int index) {
    if(disjoint[index] < 0) {
        return index;
    }

    return disjoint[index] = func(disjoint[index]);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> n;
    ve.resize(n);
    for(Edge &e : ve) {
        cin >> e.p1.x >> e.p1.y >> e.p2.x >> e.p2.y;
    }

    disjoint.assign(n, -1);
    for(int i = 0;i < n - 1;++i) {
        for(int j = i + 1;j < n;++j) {
            if(isCross(ve[i], ve[j])) {
                int left = func(i);
                int right = func(j);

                if(left != right) {
                    disjoint[left] += disjoint[right];
                    disjoint[right] = left;
                }
            }
        }
    }

    int ans = 0, cnt = 0;
    for(int i = 0;i < n;++i) {
        if(disjoint[i] < 0) {
            ans = max(ans, -disjoint[i]);
            cnt++;
        }
    }

    cout << cnt << "\n";
    cout << ans << "\n";
}