글 읽기 - 3개의 정사각형 우와 이거 ᅳᅳ;;

(追記) (追記ここまで)

3개의 정사각형 우와 이거 ᅳᅳ;;

10454번 - 세 네모

shjgkwo 10년 전 0

n = 점좌표 개수 (10만)

M = 한개의 정사각형으로 모든 점을 덮기위한 최소한의 변의 길이 (20억)

라고 할때

아무리 생각해도 O(ctnlogM) 밖에 안떠오르네요;; c = 32 항상 고정된 값이라 해도 nlogM 이 3200000이 나와버리니

둘이 곱하면 거의 1억번 계산하네요 거기에 케이스가 2개 이상 되는 순간 시간초과...

좋은 방법 어디 없을까요...

#include <stdio.h>
#include <string.h>
struct bung {
	int x;
	int y;
}o[100001];
int n;
int side;
bool sw;
short chk[100001];
int _abs(int x) {
	return x < 0 ? -x : x;
}
void sub(int minx, int miny, int maxx, int maxy, short cnt) {
	if (cnt == 2) {
		if (maxx - minx <= side && maxy - miny <= side) sw = true;
		return;
	}
	int i;
	int savminx, savminy;
	int savmaxx, savmaxy;
	// right upside
	if (sw) return;
	savminx = 0x7fffffff, savminy = 0x7fffffff;
	savmaxx = -0x7fffffff, savmaxy = -0x7fffffff;
	for (i = 0; i < n; i++) {
		if (chk[i] != 0) continue;
		if (_abs(minx - o[i].x) <= side && _abs(miny - o[i].y) <= side) chk[i] = cnt + 1;
		else {
			if (o[i].x > savmaxx) savmaxx = o[i].x;
			if (o[i].x < savminx) savminx = o[i].x;
			if (o[i].y > savmaxy) savmaxy = o[i].y;
			if (o[i].y < savminy) savminy = o[i].y;
		}
	}
	if (savminx != minx || savmaxx != maxx || savminy != miny || savmaxy != maxy) sub(savminx, savminy, savmaxx, savmaxy, cnt + 1);
	for (i = 0; i < n; i++) if (chk[i] == cnt+1) chk[i] = 0;
	// left upside
	if (sw) return;
	savminx = 0x7fffffff, savminy = 0x7fffffff;
	savmaxx = -0x7fffffff, savmaxy = -0x7fffffff;
	for (i = 0; i < n; i++) {
		if (chk[i] != 0) continue;
		if (_abs(maxx - o[i].x) <= side && _abs(miny - o[i].y) <= side) chk[i] = cnt + 1;
		else {
			if (o[i].x > savmaxx) savmaxx = o[i].x;
			if (o[i].x < savminx) savminx = o[i].x;
			if (o[i].y > savmaxy) savmaxy = o[i].y;
			if (o[i].y < savminy) savminy = o[i].y;
		}
	}
	if(savminx != minx || savmaxx != maxx || savminy != miny || savmaxy != maxy) sub(savminx, savminy, savmaxx, savmaxy, cnt + 1);
	for (i = 0; i < n; i++) if (chk[i] == cnt + 1) chk[i] = 0;
	// right downside
	if (sw) return;
	savminx = 0x7fffffff, savminy = 0x7fffffff;
	savmaxx = -0x7fffffff, savmaxy = -0x7fffffff;
	for (i = 0; i < n; i++) {
		if (chk[i] != 0) continue;
		if (_abs(minx - o[i].x) <= side && _abs(maxy - o[i].y) <= side) chk[i] = cnt + 1;
		else {
			if (o[i].x > savmaxx) savmaxx = o[i].x;
			if (o[i].x < savminx) savminx = o[i].x;
			if (o[i].y > savmaxy) savmaxy = o[i].y;
			if (o[i].y < savminy) savminy = o[i].y;
		}
	}
	if (savminx != minx || savmaxx != maxx || savminy != miny || savmaxy != maxy) sub(savminx, savminy, savmaxx, savmaxy, cnt + 1);
	for (i = 0; i < n; i++) if (chk[i] == cnt + 1) chk[i] = 0;
	// left downside
	if (sw) return;
	savminx = 0x7fffffff, savminy = 0x7fffffff;
	savmaxx = -0x7fffffff, savmaxy = -0x7fffffff;
	for (i = 0; i < n; i++) {
		if (chk[i] != 0) continue;
		if (_abs(maxx - o[i].x) <= side && _abs(maxy - o[i].y) <= side) chk[i] = cnt + 1;
		else {
			if (o[i].x > savmaxx) savmaxx = o[i].x;
			if (o[i].x < savminx) savminx = o[i].x;
			if (o[i].y > savmaxy) savmaxy = o[i].y;
			if (o[i].y < savminy) savminy = o[i].y;
		}
	}
	if (savminx != minx || savmaxx != maxx || savminy != miny || savmaxy != maxy) sub(savminx, savminy, savmaxx, savmaxy, cnt + 1);
	for (i = 0; i < n; i++) if (chk[i] == cnt + 1) chk[i] = 0;
}
int main() {
	int t, i;
	int maxx, minx;
	int maxy, miny;
	int st, ed, mid;
	freopen("input.txt", "rt", stdin);
	scanf("%d", &t);
	memset(chk, 0, sizeof(chk));
	while (t--) {
		maxx = -0x7fffffff, minx = 0x7fffffff;
		maxy = -0x7fffffff, miny = 0x7fffffff;
		scanf("%d", &n);
		for (i = 0; i < n; i++) {
			scanf("%d %d", &o[i].x, &o[i].y);
			if (o[i].x > maxx) maxx = o[i].x;
			if (o[i].x < minx) minx = o[i].x;
			if (o[i].y > maxy) maxy = o[i].y;
			if (o[i].y < miny) miny = o[i].y;
		}
		st = 0;
		ed = maxy - miny > maxx - minx ? maxy - miny : maxx - minx;
		while (st < ed) {
			mid = (st + ed) / 2;
			sw = false;
			side = mid;
			sub(minx, miny, maxx, maxy, 0);
			if (sw) ed = mid;
			else st = mid + 1;
		}
		printf("%d\n", ed);
	}
	return 0;
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC