글 읽기 - 이 상황이 적응이 안돼요

shjgkwo 5년 전 0

내일이 올림피아드인데 미친짓하는 고등학생입니다.

근데 신경쓰여서 말이죠..

대체 왜이러는 걸까요? 이게 왜 100점 일까요?

분할정복법을 사용하면 추가적으로 검사하는 부분의 점개수가 기껏해야 6개 아래라는 말을 듣고 짜봤다가

계속 시간초과가 나길래 이게 어떻게 된일이지 하고 저런 코드를 넣었더니... 100점이 나오네요.

혼란스럽습니다.

#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

#define rep(x) ((x) * (x))
#define _mindist(x, y) ((x) < (y) ? (x) : (y))

struct bung {
	int x;
	int y;
}o[100002];
bool fsort(bung a, bung b) {
	if (a.x != b.x) return a.x < b.x;
	else return a.y < b.y;
}
int n;
int ss[2][17];
int findpair(int st, int ed) {
	if (ed - st > 1) {
		int mid = (st + ed) / 2;

		int d1, d2;
		int min_d;

		d1 = findpair(st, mid);
		d2 = findpair(mid + 1, ed);

		min_d = _mindist(d1, d2);

		int s = (int)sqrt(min_d);
		int sx = o[mid].x, sy = o[mid].y;
		int i, j;
		int sizet = 0;
		for (i = st; i <= ed; i++) {
			if (sx - s <= o[i].x && sx + s >= o[i].x && sy - s <= o[i].y && sy + s >= o[i].y) {
				ss[0][sizet] = o[i].x;
				ss[1][sizet++] = o[i].y;
			}
		}
		int d;
		if (sizet >= 17) return 0; // sizet 가 17이 넘어가는 경우 0을 내뱉도록 시키는 말도안돼는 부분
		for (i = 0; i < sizet; i++) {
			for (j = i + 1; j < sizet; j++) {
				d = rep(ss[0][i] - ss[0][j]) + rep(ss[1][i] - ss[1][j]);
				min_d = _mindist(min_d, d);
			}
		}

		sx = o[mid + 1].x, sy = o[mid + 1].y;
		sizet = 0;
		for (i = st; i <= ed; i++) {
			if (sx - s <= o[i].x && sx + s >= o[i].x && sy - s <= o[i].y && sy + s >= o[i].y) {
				ss[0][sizet] = o[i].x;
				ss[1][sizet++] = o[i].y;
			}
		}
		if (sizet >= 17) return 0; // sizet 가 17이 넘어가는 경우 0을 내뱉도록 시키는 말도안돼는 부분

		for (i = 0; i < sizet; i++) {
			for (j = i + 1; j < sizet; j++) {
				d = rep(ss[0][i] - ss[0][j]) + rep(ss[1][i] - ss[1][j]);
				min_d = _mindist(min_d, d);
			}
		}


		return min_d;
	}
	else {
		int i, j;
		int d;
		int min_d = 0x7fffffff;
		for (i = st; i <= ed; i++) {
			for (j = i + 1; j <= ed; j++) {
				d = rep(o[i].x - o[j].x) + rep(o[i].y - o[j].y);
				min_d = _mindist(min_d, d);
			}
		}
		return min_d;
	}
}
int main() {
	int i;
	freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	for (i = 1; i <= n; i++) scanf("%d %d", &o[i].x, &o[i].y);
	std::sort(o + 1, o + n + 1, fsort);
	printf("%d", findpair(1, n));
	return 0;
}

shjgkwo 5년 전 0

혹시 데이터 중에 중복데이터가 100000개 들어오는게 있습니까?

만약 사실이라면... ㅠㅠ

shjgkwo 5년 전 0

맞네.. 중복데이터 100000개라니 ㅠㅠ

문제에 중복데이터가 들어오지 않는다는 말은 없었는데.. ㅠㅠㅠㅠ

hakgb11 5년 전 0

시험 잘보고 오세요 ㅠㅠ

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

문제

문제

출처

ICPC

이 상황이 적응이 안돼요

shjgkwo 5년 전 0

shjgkwo 5년 전 0

shjgkwo 5년 전 0

hakgb11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말