BOJ 10255 교차점


사용한 알고리즘

  • CCW

알고리즘 설명

  • 기하문제는 무섭다 ㅠ_ㅠ
  • 나름 기하의 기초? 인거 같다.
  • 두 선과의 교점 여부를 CCW로 판단하면된다.
  • 예외처리로 선이 모서리에서 곂치는 경우 2번 세어진다. 중복을 제거해주자.
  • 두선이 여러 점에서 곂치는 조건은 CCW 값이 0이면서 두선이 곂치는 경우(단 모서리 조건은 아님)
  • 이를 구현하면 된다

풀이

// baekjoon 10255_2 yechan
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct Point{
    int x, y;
    Point():x(0), y(0){}
    Point(int x, int y):x(x), y(y){}
    bool operator>(const Point &o) {
        return (o.x == x) ? y > o.y : x > o.x;
    }
    bool operator<(const Point &o) {
        return (o.x == x) ? y < o.y : x < o.x;
    }
    bool operator<=(const Point &o) {
        return (o.x == x) ? y <= o.y : x <= o.x;
    }
    bool operator==(const Point &o) {
        return (x == o.x) && (y == o.y);
    }
};

struct Line{
    Point pos[2];
    Line(){};
    Line(Point a, Point b){ pos[0]=a; pos[1]=b; }
};

int getCCW(Point a, Point b, Point c) {
    int res = (a.x*b.y + b.x*c.y + c.x*a.y);
    res -= (a.x*c.y + b.x*a.y + c.x*b.y);
    return (res) ? ((res < 0) ? -1 : 1) : 0;
}

int isISTPoint(Line rline, Line line) {
    Point a = line.pos[0];
    Point b = line.pos[1];
    Point c = rline.pos[0];
    Point d = rline.pos[1];

    int ccw[4];
    ccw[0] = getCCW(a, b, c), ccw[1] = getCCW(a, b, d);
    ccw[2] = getCCW(c, d, a), ccw[3] = getCCW(c, d, b);

    int ab = ccw[0]*ccw[1];
    int cd = ccw[2]*ccw[3];
    if (ccw[0] == 0 && ccw[0] == ccw[1]) {
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        if (ccw[2] == 0 && ccw[2] == ccw[3]) { // 평행할때
            if (b < c || d < a) return 0; // 평행 하지만 겹치지 않음
            if (b == c || d == a) return 1; // 1점만 겹침
            return -1; // 해가 많음 (4)
        }
        return 1;
    }
    return (ab <= 0 && cd <= 0);
}

int Solve(vector<Line> rect, Line line) {
    int ans = 0;
    for (int i=0; i<4; i++){
        int tmp = isISTPoint(rect[i], line);
        if (tmp == -1) return 4;
        ans += tmp;
        if (isISTPoint(Line(rect[i].pos[0], rect[i].pos[0]), line)) ans--; // 각 모서리 중복 제거
    }
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int i=0; i<T; i++) {
        vector<Line> rect;
        Line line;
        int xmin, ymin, xmax, ymax;
        scanf("%d%d%d%d", &xmin, &ymin, &xmax, &ymax);
        rect.push_back(Line(Point(xmin, ymin), Point(xmax,ymin)));
        rect.push_back(Line(Point(xmax, ymin), Point(xmax,ymax)));
        rect.push_back(Line(Point(xmax, ymax), Point(xmin,ymax)));
        rect.push_back(Line(Point(xmin, ymax), Point(xmin,ymin)));
        scanf("%d%d%d%d", &xmin, &ymin, &xmax, &ymax);
        line = Line(Point(xmin, ymin), Point(xmax, ymax));
        int ret = Solve(rect, line);
        printf("%d\n", ret);
    }
    return 0;
}



© 2020.08. by fbdp1202

Powered by theorydb