글 읽기 - 왜 틀렸는지 모르겠어요

math_rabbit_1028 3년 전 0

봉우리를 구간으로 표현해 문제를 풀었습니다. 틀린부분 알려주시면 감사하겠습니다.

//14865 - 곡선 자르기
#include <iostream>
#include <algorithm>
using namespace std;
struct two {
	int s, f;
};
int n, loc[1010101][2], t[1010101], res1 = 0, res2 = 0, temp = -2147000000;
two interval[1010101];

bool compare(two a, two b) {
	return a.s < b.s;
}

int main() {
	int r = 0;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> loc[i][0] >> loc[i][1];
	for (int i = 1; i <= n - 1; i++) {
		if (loc[i][0] == loc[i + 1][0] && ((loc[i][1] < 0 && 0 < loc[i + 1][1])
			|| (loc[i][1] > 0 && 0 > loc[i + 1][1]))) {
			t[++r] = i;
		}
	}
	if (loc[n][0] == loc[1][0] && ((loc[n][1] < 0 && 0 < loc[1][1])
		|| (loc[n][1] > 0 && 0 > loc[1][1]))) {
		t[++r] = n;
	}
	for (int i = 1; i <= r / 2; i++) {
		interval[i].s = min(loc[t[2 * i - 1]][0], loc[t[2 * i]][0]);
		interval[i].f = max(loc[t[2 * i - 1]][0], loc[t[2 * i]][0]);
	}
	sort(interval + 1, interval + r / 2 + 1, compare);
	for (int i = 1; i <= r / 2; i++) {
		if (temp < interval[i].s) res1++;
		if (temp < interval[i].f) temp = interval[i].f;
		if (i == r / 2 || interval[i].f < interval[i + 1].s) res2++;
	}
	cout << res1 << " " << res2 << "\n";
	return 0;
}

seico75 3년 전 2

14
-4 3
3 3
3 -2
1 -2
1 1
-1 1
-1 -1
-2 -1
-2 2
-3 2
-3 -2
0 -2
0 -4
-4 -4

문제의 첫번째 예제에서 시작점만 바꾸었고, 답은 예제1과 같아야 할 것 같습니다.

math_rabbit_1028 3년 전 0

감사합니다. 덕분에 잘 해결할 수 있었습니다.

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠어요

math_rabbit_1028 3년 전 0

seico75 3년 전 2

math_rabbit_1028 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말