글 읽기 - 1858 맞는 것 같은데 자꾸 WA 나오네요ㅠㅠ

h0ngjun7 10년 전 0

저는 x값 순으로 정렬한 다음에 인접한 원소를 비교하는 방식으로 풀었습니다.

점 3개를 골라서 만들 수 있는 기울기 중, 가장 큰 기울기는 x값 순으로 정렬했을 때에 인접한 것에서만 발생하는 것에서 착안하여 아래 소스코드처럼 풀었는데 WA가 아주 빠른 속도로 나오네요ㅠㅠ

도와주시면 감사하겠습니다.

#include <stdio.h>
#include <algorithm>
using namespace std;
struct data {
	int x, y, idx;
} p[50005];
int n;
inline bool cmp(data d1, data d2) {
	//x좌표 같으면 그 중에 인덱스 가장 작은 2개가 답
	if (d1.x == d2.x) return d1.idx < d2.idx;
	return d1.x < d2.x;
}
inline double f(double x) { //절댓값/
	if (x >= 0.0) return x;
	return -x;
}
double sol = -0.1;
int res1, res2, m1, m2;
int main() {
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d",&p[i].x,&p[i].y);
		p[i].idx = i;
	}
	sort(p+1, p+n+1, cmp); //x순 정렬
	for (int i = 1; i < n; i++) {
		//인덱스가 작은 거 : m1, 큰 거 : m2
		if (p[i].idx < p[i+1].idx) m1 = p[i].idx, m2 = p[i+1].idx;
		else m1 = p[i+1].idx, m2 = p[i].idx;
		if (p[i].x == p[i+1].x) { //기울기가 무한대면
			if (sol < -0.5) { //기존에 무한대가 나온 적이 있으면
				//인덱스만 갱신
				if (m1 < res1 || (m1 == res1 && m2 < res2)) res1 = m1, res2 = m2;
			} else { //무한대가 처음 나왔으면
				sol = -1;
				res1 = m1, res2 = m2;
			}
		} else {
			if (sol < -0.5) continue;
			//기울기가 무한대가 아니면
			if (sol+1e-7 < f((double)(p[i+1].y-p[i].y)/(double)(p[i+1].x-p[i].x))) {
				//기울기가 더 커서 갱신
				sol = f((double)(p[i+1].y-p[i].y)/(double)(p[i+1].x-p[i].x));
				res1 = m1, res2 = m2;
			} else if (f((double)(p[i+1].y-p[i].y)/(double)(p[i+1].x-p[i].x) - sol) < 1e-7) {
				//기울기가 같고 인덱스 갱신
				if (m1 < res1 || (m1 == res1 && m2 < res2)) res1 = m1, res2 = m2;
			}
		}
	}
	//답 출력
	printf("%d %d",res1,res2);
	return 0;
}

baekjoon 10년 전 1

기울기가 같은 경우 처리를 잘못 한 것 같습니다.

아래와 같은 데이터에서 틀리는 것 같네요.

3
0
-4
-2

h0ngjun7 10년 전 0

덕분에 풀었습니다!! 감사합니다 관리자님!ㅎㅎㅎ

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

문제

문제

출처

ICPC

1858 맞는 것 같은데 자꾸 WA 나오네요ㅠㅠ

h0ngjun7 10년 전 0

baekjoon 10년 전 1

h0ngjun7 10년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말