글 읽기 - 반례가 있을까요?

jkjan 4년 전 0

제 방법은.. 진짜 직관적으로..

이중 포문을 돌리면서 두 직선이 만나면 그래프의 인접리스트에 추가하고

마지막에 dfs 를 돌리는 건데요

만나는 걸 어떻게 보느냐 하면..

두 직선의 방정식을 구해서

방정식의 계수에 따라서 평행, 일치 여부를 구하고..

일치면 그 선분이 만나긴 하는지

둘 다 아니면 교점이 두 선분 위에 존재하는지를 구하는 방법입니다.

직선의 방정식은 나눌 거 다 나눠주고.. ax + by = c 의 꼴입니다..

b는 1 또는 0의 값을 가집니다.

게시판에 있는 tc들은 다 맞긴 하는데...

도대체 어디가 잘못된 것인지 모르겠네요...

그리고 교점을 구하는 intersect 함수에서..

조건문에 걸리지 않는 경우가 있나 하고 제가 계속 체크를 해봤는데..

위의 평행, 일치 여부에서 판단되지 않는 방정식만 이 과정을 거치게 됩니다..

왜냐면 2, 2랑 3, 3 유형은 무조건 평행이어서 .. (y의 계수가 무조건 1 또는 0이기 때문)

또한 선분의 직선 방정식이.. 두 직선이 일치한다고 나올 때..

선분이 일단 안 겹치는지를 체크하는데

거기서 false로 return이 안 되면 무조건 겹친다고 봅니다.

자료형도 double 이기도 하고..

제가 논리적으로 어떻게 틀린 건지.. 잘 모르겠습니다..

그래도 함수로 모듈화는 해놓아서..

코드를 읽어보신다면 아마 문제점은 doTheyMeet나 intersect 함수의 조건문 속에 있지 않을까 싶습니다..

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct _Line {
    double x1, y1, x2, y2;
} Line;

typedef struct _Equation {
    double a, b, c;
} Equation;

typedef struct _Pos {
    double x, y;
} Pos;

int input();
bool doTheyMeet(Line line1, Line line2);
void dfs(int);

vector<Line> lines;
vector<int> lineGraph[3000];
bool visited[3000] = {false,};
int groupSize = 0;

int main() {
    int N;
    int maxGroupSize = 0;
    int groupCnt = 0;

    N = input();

    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            dfs(i);
            maxGroupSize = max(maxGroupSize, groupSize);
            groupSize = 0;
            groupCnt++;
        }
    }

    cout << groupCnt << endl;
    cout << maxGroupSize << endl;

    return 0;
}

int input() {
    int N;
    cin >> N;
    double x1, y1, x2, y2;
    for (int i = 0; i < N; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        Line line = {x1, y1, x2, y2};
        lines.push_back(line);

        for (int j = 0; j < i; j++) {
            if (doTheyMeet(lines[j], line)) {
                lineGraph[i].push_back(j);
                lineGraph[j].push_back(i);
            }
        }
    }

    return N;
}

Equation makeItEquation(Line line) {
    // ax + by = c
    if (line.x1 == line.x2)
        return {1, 0, line.x1};
    double cof = ((line.y2 - line.y1) / (line.x2 - line.x1));
    return {-cof, 1, (line.y1 - line.x1 * cof)};
}

bool isIn(double start, double it, double end) {
    if (start <= end)
        return (start <= it && it <= end);
    else
        return (end <= it && it <= start);
}

int equationType(Equation equation) {
    if (equation.a != 0 && equation.b == 1)
        return 1;
    else if (equation.a == 1 && equation.b == 0)
        return 2;
    else
        return 3;
}

Pos intersect(Equation equation1, Equation equation2) {
    double x, y;
    /* 1. ax + y = c
     * 2. x = c
     * 3. y = c
     * */

    // 방정식 중 하나가 3유형
    if (equationType(equation1) == 3 || equationType(equation2) == 3) {
        if (equationType(equation1) == 3)
            swap(equation1, equation2);
        y = equation2.c;

        // 1 3
        if (equationType(equation1) == 1) {
            x = ((equation1.c - y) /equation1.a);
        }

        // 2 3
        else {
            x = equation1.c;
        }
    }

    // 방정식 중 하나가 1유형
    else if (equationType(equation1) == 1 || equationType(equation2) == 1) {
        if (equationType(equation2) == 1)
            swap(equation1, equation2);

        // 1 2
        if (equationType(equation2) == 2) {
            x = equation2.c;
            y = equation1.c - equation1.a * x;
        }

        // 1 1
        else {
            x = (equation1.c - equation2.c)/(equation1.a - equation2.a);
            y = equation1.c - equation1.a * x;
        }
    }

    return Pos{x, y};
}

bool doTheyMeet(Line line1, Line line2) {
    Equation equation1 = makeItEquation(line1);
    Equation equation2 = makeItEquation(line2);

    if (equation1.a == equation2.a && equation1.b == equation2.b) {
        // 두 직선 평행
        if (equation1.c != equation2.c) {
            return false;
        }

        // 두 직선 일치
        else {
            // 둘 다 y축에 평행한 선분
            if (equation1.b == 0 && equation2.b == 0) {
                if (line1.y1 > line2.y1)
                    swap(line1, line2);

                int y1 = max(line1.y1, line1.y2);
                int y2 = min(line2.y1, line2.y2);

                if (y1 < y2) {
                    // 선분 안 만남
                    return false;
                }
            }

            else {
                if (line1.x1 > line2. x2)
                    swap(line1, line2);

                int x1 = max(line1.x1, line1.x2);
                int x2 = min(line2.x1, line2.x2);

                if (x1 < x2) {
                    // 선분 안 만남
                    return false;
                }
            }

            return true;
        }
    }

    // 교차
    Pos point = intersect(equation1, equation2);

    return (isIn(line1.x1, point.x, line1.x2) &&
            isIn(line1.y1, point.y, line1.y2) &&
            isIn(line2.x1, point.x, line2.x2) &&
            isIn(line2.y1, point.y, line2.y2));
}

void dfs(int v) {
    visited[v] = true;
    groupSize++;
    for (int &itor : lineGraph[v]) {
        if (!visited[itor]) {
            dfs(itor);
        }
    }
}

ha_ram 4년 전 2

실수를 가지고 연산하는것과 나눗셈을 하는것은 오차가 발생할 수 있습니다.

방정식으로 하지 마시고

구글에 검색해보면 CCW알고리즘이라고

선분의 교차여부를 판별하는 알고리즘이 있는데

이것으로 해보시는걸 추천합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 있을까요?

jkjan 4년 전 0

ha_ram 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말