글 읽기 - 두 코드의 다른 점을 전혀 모르겠습니다.

rdd6584 4년 전 0

위 코드는 WA를 받으며, 아래는 AC를 받는 코드입니다.

두 코드의 다른 점은 for(j = i + 1; j < n; j++)이냐,

for (j = 0; j < i; j++)이냐. 두 차이밖에 없습니다.

두 경우가 다르게 나오는 예제가 있다는 사실이 전혀 납득이 가지 않는데. 혹시 어떤 경우에서 그럴 수 있을까요?

// WA/////////////////
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#include <iostream>
#include <string>
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pci pair<char,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pdi pair<double,int>
#define mod 1000000007
#define mod1 1000000009
#define mod2 1000000021
#define INF 10000000
#define MAX 10000000
long double PI = 3.141592653589793238462643383279502884197;
using namespace std;

/* 🐣🐥 */
struct info {
	int a, b, c, d;
} arr[3001];

int p[3001], sz[3001];

ll cr(int x1, int y1, int x2, int y2) {
	return (ll)x1 * y2 - (ll)y1 * x2;
}

int find(int a) {
	if (p[a] == -1) return a;
	return p[a] = find(p[a]);
}
void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	sz[a] += sz[b];
	p[b] = a;
}
bool isTrue(info a, info b) {
	if (a.a > a.c) swap(a.a, a.c);
	if (a.b > a.d) swap(a.b, a.d);
	if (a.a <= b.a && b.a <= a.c && a.b <= b.b && b.b <= a.d) return true;
	if (a.a <= b.c && b.c <= a.c && a.b <= b.d && b.d <= a.d) return true;
	return false;
}
int main() {
	memset(p, -1, sizeof(p));

	int n;
	scanf("%d", &n);
	fill(sz, sz + n, 1);

	for (int i = 0; i < n; i++)
		scanf("%d %d %d %d", &arr[i].a, &arr[i].b, &arr[i].c, &arr[i].d);

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ll aa, bb;
			aa = cr(arr[i].c - arr[i].a, arr[i].d - arr[i].b,
				arr[j].a - arr[i].a, arr[j].b - arr[i].b);

			bb = cr(arr[i].c - arr[i].a, arr[i].d - arr[i].b,
				arr[j].c - arr[i].a, arr[j].d - arr[i].b);

			if (aa * bb > 0) continue;

			aa = cr(arr[j].c - arr[j].a, arr[j].d - arr[j].b,
				arr[i].a - arr[j].a, arr[i].b - arr[j].b);

			bb = cr(arr[j].c - arr[j].a, arr[j].d - arr[j].b,
				arr[i].c - arr[j].a, arr[i].d - arr[j].b);

			if (aa * bb > 0) continue;

			if (aa == 0 && bb == 0 && !isTrue(arr[i], arr[j])) continue;
			merge(i, j);
		}
	}

	int ans = 0, mx = 0;
	for (int i = 0; i < n; i++)
		if (find(i) == i) {
			ans++;
			mx = max(mx, sz[i]);
		}
	printf("%d\n%d", ans, mx);

	return 0;
}






// AC/////////////////
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#include <iostream>
#include <string>
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pci pair<char,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pdi pair<double,int>
#define mod 1000000007
#define mod1 1000000009
#define mod2 1000000021
#define INF 10000000
#define MAX 10000000
long double PI = 3.141592653589793238462643383279502884197;
using namespace std;

/* 🐣🐥 */
struct info {
	int a, b, c, d;
} arr[3001];

int p[3001], sz[3001];

ll cr(int x1, int y1, int x2, int y2) {
	return (ll)x1 * y2 - (ll)y1 * x2;
}

int find(int a) {
	if (p[a] == -1) return a;
	return p[a] = find(p[a]);
}
void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	sz[a] += sz[b];
	p[b] = a;
}
bool isTrue(info a, info b) {
	if (a.a > a.c) swap(a.a, a.c);
	if (a.b > a.d) swap(a.b, a.d);
	if (a.a <= b.a && b.a <= a.c && a.b <= b.b && b.b <= a.d) return true;
	if (a.a <= b.c && b.c <= a.c && a.b <= b.d && b.d <= a.d) return true;
	return false;
}
int main() {
	memset(p, -1, sizeof(p));

	int n;
	scanf("%d", &n);
	fill(sz, sz + n, 1);

	for (int i = 0; i < n; i++)
		scanf("%d %d %d %d", &arr[i].a, &arr[i].b, &arr[i].c, &arr[i].d);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			ll aa, bb;
			aa = cr(arr[i].c - arr[i].a, arr[i].d - arr[i].b,
				arr[j].a - arr[i].a, arr[j].b - arr[i].b);

			bb = cr(arr[i].c - arr[i].a, arr[i].d - arr[i].b,
				arr[j].c - arr[i].a, arr[j].d - arr[i].b);

			if (aa * bb > 0) continue;

			aa = cr(arr[j].c - arr[j].a, arr[j].d - arr[j].b,
				arr[i].a - arr[j].a, arr[i].b - arr[j].b);

			bb = cr(arr[j].c - arr[j].a, arr[j].d - arr[j].b,
				arr[i].c - arr[j].a, arr[i].d - arr[j].b);

			if (aa * bb > 0) continue;

			if (aa == 0 && bb == 0 && !isTrue(arr[i], arr[j])) continue;
			merge(i, j);
		}
	}

	int ans = 0, mx = 0;
	for (int i = 0; i < n; i++)
		if (find(i) == i) {
			ans++;
			mx = max(mx, sz[i]);
		}
	printf("%d\n%d", ans, mx);

	return 0;
}

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

문제

문제

출처

ICPC

두 코드의 다른 점을 전혀 모르겠습니다.

rdd6584 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말