글 읽기 - C++메모리초과

look014 1년 전 0

아무리 봐도 왜 메모리 초과가 나는지 이해가 안갑니다.

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

using namespace std;

typedef pair<int, int> PII;
int N;

typedef struct vec {
	PII first;
	PII second;
}vec;

vec v[3001];
int p[3001];
int cnt[3001];
int ccw(PII p1, PII p2, PII p3) {
	int cross_product = (p2.first - p1.first) * (p3.second - p1.second) - (p3.first - p1.first) * (p2.second - p1.second);
	if (cross_product > 0) {
		return 1;
	}
	else if (cross_product < 0) {
		return -1;
	}
	else {
		return 0;
	}
}

int getp(int i) {
	if (i == p[i]) return i;
	return p[i] = getp(i);
}
void join(int i, int j) {
	i = getp(i);
	j = getp(j);
	if (i < j) p[j] = i;
	else p[i]= j;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> v[i].first.first >> v[i].first.second >> v[i].second.first >> v[i].second.second;
	}

	for (int i = 0; i < N; i++)
		p[i] = i;

	PII p1, p2, p3, p4;
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			 p1 = v[i].first, p2 = v[i].second, p3 = v[j].first, p4 = v[j].second;
			if ((ccw(p1, p2, p3) * ccw(p1, p2, p4) <=0) && (ccw(p3, p4, p1) * ccw(p3, p4, p2) <=0)) {
				if ((p1.first > p3.first && p1.first > p4.first && p2.first > p3.first && p2.first > p4.first) ||
					(p1.first < p3.first && p1.first < p4.first && p2.first < p3.first && p2.first < p4.first)) continue;
				else if ((p1.second > p3.second && p1.second > p4.second && p2.second > p3.second && p2.second > p4.second)
					|| (p1.second < p3.second && p1.second < p4.second && p2.second < p3.second && p2.second < p4.second)) continue;
				else {
					join(i,j);
				}
			}
		}
	}

	int MaxG = 0, groupcnt = 0;
	for (int i = 0; i < N; i++) {
		cnt[getp(i)]++;
	}
	for (int i = 0; i < N; i++) {
		if (cnt[i] != 0) groupcnt++;
		MaxG = max(cnt[i], MaxG);
	}
	cout << groupcnt << endl<<MaxG<<endl;
}

zenith82114 1년 전 0

34줄에서 무한 재귀에 빠집니다.

return p[i] = getp(p[i]); 로 고치면 될 것 같네요.

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

문제

문제

출처

ICPC

C++메모리초과

look014 1년 전 0

zenith82114 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말