글 읽기 - 선분교차2, 33%에서 틀리네요..

kth990303 3년 전 0

선분교차 2 문제를 풀다가 WA를 받고, 계속 반례를 찾아보다가 반례를 찾지 못해 질문드립니다 ㅠㅠ

선분교차1 문제 풀 때처럼 ccw 알고리즘을 진행하되, 두 선분이 서로 평행할 때, 예외처리 작업을 해주었는데, 이 처리부분에서 문제가 생기는 듯 합니다.

반례가 생길 때마다 코드에 추가하다보니, 가독성이 조금 떨어질 수 있어 최대한 주석을 붙여보았습니다.

반례나 틀린 부분 찾아주신다면 정말 감사하겠습니다!

#include <iostream>
using namespace std;
typedef long long ll;
struct Point {
	ll x, y;
};
Point p[4];
// ccw 알고리즘 진행, long long 타입 반환
ll ccw(Point p1, Point p2, Point p3) {
	ll ret = p1.x * p2.y + p2.x * p3.y + p3.x * p1.y
		- (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x);
	if (ret > 0) return 1;
	else if (ret < 0) return -1;
	else return 0;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
    
    // 좌표 입력받기
	for (int i = 0; i < 4; i++) {
		cin >> p[i].x >> p[i].y;
	}
    // ccw진행
	ll ans1 = ccw(p[0], p[1], p[2]) * ccw(p[0], p[1], p[3]);
	ll ans2 = ccw(p[2], p[3], p[0]) * ccw(p[2], p[3], p[1]);
	if (ans1 <= 0 && ans2 <= 0) {
        // 서로 평행할 때 예외처리
		if (!ans1 && !ans2) {
            // p[0]는 p[1]보다 작게
			if (p[0].x > p[1].x && p[0].y>p[1].y)
				swap(p[0], p[1]);
            // p[2]는 p[3]보다 작게
			if (p[2].x > p[3].x && p[2].y>p[3].y)
				swap(p[2], p[3]);
            // P0 P2 P1 P3일 때 서로 겹침
			ll l1 = p[0].x - p[3].x;
			ll l2 = p[2].x - p[1].x;
			if (l1 * l2 >= 0) {
                // x좌표가 서로 같을 때의 반례 때문에 y좌표로도 같은 행위 반복
				ll l3 = p[0].y - p[3].y;
				ll l4 = p[2].y - p[1].y;
				if (l3 * l4 >= 0)
					cout << 1 << "\n";
				else
					cout << "0\n";
			}
			else cout<<"0\n";
		}
        // 교차 조건 만족 (평행하지 않을 경우)
		else
			cout << 1 << "\n";
	}
	else
		cout << 0 << "\n";
}

djs100201 3년 전 2

0 3 0 0

0 2 0 4

Ans:1

Output:0

선분이 평행할때 판단하는 부분을 다시 짜야 할 거 같습니다

kth990303 3년 전 0

@djs100201

이문제 예전에 실패하고 지금 풀어서 ac받았는데 이때도 도움주셨네요. 덕분에 해결했습니다. 4181번 Convex hull 문제에도 도움받았는데 정말 감사합니다. 기하의 왕이시군요..

djs100201 3년 전 0

기하는 팀원들에게 맡기려구요 ... ㅋㅋㅋㅋ 기하 시러요 ㅠㅠ

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

문제

문제

출처

ICPC

선분교차2, 33%에서 틀리네요..

kth990303 3년 전 0

djs100201 3년 전 2

kth990303 3년 전 0

djs100201 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말