글 읽기 - 어디가 잘못되었을까요?(c++,ccw,union-find)

112224 1년 전 0

로직이나 오버플로우 관련해서는 문제가 나지 않는 것 같은데 WA를 받았습니다.

고쳐보려고 하는데 어디가 문제인지 보이질 않아서요 ㅠㅠ

문제인 부분이나 반례주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int si = 3010;
typedef long long ll;
typedef struct p
{
	ll x, y;
}p;
typedef struct li
{
	p p1, p2;
}li;
li a[si];
int pare[si];
int group[si];

int find(int p)
{
	if (p == pare[p])
		return p;
	return pare[p]=find(pare[p]);
}
int uni(int i, int j)
{
	int b1 = find(i),b2=find(j);
	if (group[b1] < group[b2])    
		swap(b1, b2);

	pare[b2] = b1;    

	group[b1] += group[b2];
	return group[b1];    //갱신된 값 리턴
}
int ccw(p q, p w, p e)    //점3개에 대해서 ccw 계산
{
	ll tmp1 = (w.x - q.x)*(e.y - q.y), tmp2 = (w.y - q.y)*(e.x - q.x);    //ll범위로 오버플로 방지
	if (tmp1 - tmp2 == 0) return 0;
	else
	{
		return tmp1 - tmp2 > 0 ? 1 : -1;
	}
}
ll cal(p i, p j)
{
	return (i.x - j.x)*(i.x - j.x) + (i.y - j.y)*(i.y - j.y);    //ll범위
}
bool dist(li u,li v)
{
	ll d1 = cal(u.p1, u.p2);
	ll d3 = min(cal(u.p1, v.p1), cal(u.p1,v.p2)), 
		d4 = min(cal(u.p2, v.p1), cal(u.p2, v.p2));
	return d1 >= max(d3, d4);
}
bool cross(li u, li v)        //교차여부
{
	int f1 = ccw(u.p1, u.p2, v.p1)*ccw(u.p1, u.p2, v.p2);
	if (f1 > 0) return false;
	else
	{
		int f2 = ccw(v.p1, v.p2, u.p1)*ccw(v.p1, v.p2, u.p2);
		if (f2 > 0)return false;
		else if (f1 == 0 && f2 == 0)return dist(u, v);
		else return true;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int n; cin >> n;
	for (int i = 1; i <= n; i++)        //초기화
	{
		cin >> a[i].p1.x >> a[i].p1.y >> a[i].p2.x >> a[i].p2.y;
		pare[i] = i;
		group[i] = 1;
	}
	int ans1 = 1, ans2 = 0;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j < i; j++)
		{
			if (pare[i] == pare[j])continue;    //부모가 같을 경우 넘겨줌
			if (cross(a[i], a[j]))
				ans1 = max(ans1, uni(j, i));    // 최댓값 갱신
		}

	for (int i = 1; i <= n; i++)if (pare[i] == i)ans2++;

	cout << ans2 << '\n' << ans1 << '\n';
	
}

line_jin 1년 전 1

87번째줄 부모가 같은 경우를 확인하는 것을 pair[i] == pair[j]라 해서 틀린 겁니다.

union과정에서 루트노드만 연결해주고 나머지 자식들의 배열값은 바뀌지 않았기 때문에 발생하는 문제입니다.

find(i) == find(j) 로 수정하면 정답처리 됩니다.

112224 1년 전 0

헐 감사합니다! 부모노드 갱신해 주는 걸 안하고 저리 만들어 버렸네요.

찾아주지 않으셨으면 오늘 안에 못 찾았을 것 같아요 ㅋㅋㅋㅋ 감사합니다!!

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

문제

문제

출처

ICPC

어디가 잘못되었을까요?(c++,ccw,union-find)

112224 1년 전 0

line_jin 1년 전 1

112224 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말