skeksk91   9년 전

두 점 (ax,ay)  , (bx,by)  과 나머지 점들의 거리(dist1,dist2) 를 계산 후에

교집합 여부로 방독면?을 2개 받는 곳을 알려고 했습니다.

dist1 <= r1 && dist2 <= r2     -->  AnB       ,    dist1 > r1 && dist2 > r2   -->  ~(AuB)    // 일단 이렇게하고 모든 n을 순회하면 시간초과가 납니다

무언가 이에대한 자료구조 선택을 못하고 있었습니다.

그래서 lower_bound()를 이용해서 풀 수 있을 것 같은데도 흠.. 많이 봤는데도 잘 모르겠습니다.  

되게 딱 떨어지게? 푸실 수 있는 분들 있으실 거같은데 부럽습니다. 

어떤식으로 접근해야 풀 수 있는 거죠 ?___?

mongsiry013   9년 전

문제를 풀어보진 않았는데 문제를 보니 교집합을 구할 필요는 없을 것 같아요

(전체 집의 개수) - (A지역에 속하는 집의 개수) - (B지역에 속하는 집의 개수) 가 정답이 될 것 같군요.

A지역과 B지역에 동시에 속하는 집들은 장비를 2개씩 받고 하나씩을 외부에 있는 집들에게 주니까요

skeksk91   9년 전

그렇군요 ㅠ  흐으윽 감사합니다. !!!  lower_bound 공부하고 풀어보겠습니다 ㅠ

어떻게 쓰는지 잘 몰라서 흑

h0ngjun7   9년 전

제 소스를 공개 설정 해놓았어요. 전 upper_bound를 써서 풀었는데, lower_bound랑 차이점은 같은 값이 여러 개 있을 때, 상한값을 리턴하냐, 하한값을 리턴하냐의 차이인 것 같더라구요. 참고하시길 바라요.

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