글 읽기 - [Go] 뭐가 틀린지 모르겠습니다.. 반례를 찾아주세요..

tizm423 3년 전 0

모든 사각형을 서로 탐색하게 해서 O(N²)으로 구현했는데 틀렸습니다..

혹시 어디서 틀린건지 알 수 있을까요??

package main

import (
	"bufio"
	"os"
	"strconv"
)

type box struct {
	x1, y1 int
	x2, y2 int
}

var (
	check []bool
	boxes []box
	N     int
	s     = bufio.NewScanner(os.Stdin)
	w     = bufio.NewWriter(os.Stdout)
)

func main() {
	s.Split(bufio.ScanWords)
	defer w.Flush()
	N = scanInt()
	boxes = append(boxes, box{0, 0, 0, 0})
	for i := 0; i < N; i++ {
		boxes = append(boxes, box{scanInt(), scanInt(), scanInt(), scanInt()})
	}
	check = make([]bool, N+1)

	for i := 1; i < len(boxes); i++ {
		for j := 0; j < len(boxes); j++ {
			if i!=j && overlapCheck(boxes[j], boxes[i]) {
				check[j] = true
				check[i] = true
			}
		}
	}

	count := 0
	for i := 0; i < N+1; i++ {
		if !check[i] {
			count++
		}
	}

	w.WriteString(strconv.Itoa(count) + "\n")
}

func overlapCheck(a, b box) bool {
	// a가 b보다 완전 위에 있음
	if a.y1 > b.y2 {
		return false
	}

	// a가 b보다 완전 아래에 있음
	if a.y2 < b.y1 {
		return false
	}

	// a가 b보다 완전 뒤에 있음
	if a.x2 < b.x1 {
		return false
	}

	// a가 b보다 완전 앞에 있음
	if b.x2 < a.x1 {
		return false
	}

	// a가 b 안에있음
	if a.x1 > b.x1 && a.x1 < b.x2 && a.x2 < b.x2 {
		if a.y1 > b.y1 && a.y1 < b.y2 && a.y2 < b.y2 {
			return false
		}
	}

	// b가 a 안에있음
	if b.x1 > a.x1 && b.x1 < a.x2 && b.x2 < a.x2 {
		if b.y1 > a.y1 && b.y1 < a.y2 && b.y2 < a.y2 {
			return false
		}
	}

	return true
}

func scanInt() int {
	s.Scan()
	ret, _ := strconv.Atoi(s.Text())
	return ret
}

exponential_e 3년 전 1

초기 거북이는 연필을 내리고 있는 PD 상태이므로 PU 후 사각형을 그리면 끝나는 경우니 아래 데이터에서는 1이 나오는 것이 맞다 생각합니다만,

작성자님 코드에선 2를 출력합니다. 확인 해보시기 바랍니다.

입력
1
1 1 4 4
출력
2
답
1

tizm423 3년 전 1

@exponential_e님 감사합니다.

뭐가 문제인지 알았습니다..

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

문제

문제

출처

ICPC

[Go] 뭐가 틀린지 모르겠습니다.. 반례를 찾아주세요..

tizm423 3년 전 0

exponential_e 3년 전 1

tizm423 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말