이 문제엔 어떤 방법으로 접근해야 할까?

[whatugo..(sibal214)]

내가 푼 방법으로는 타임아웃만 뜬다...

어떻게 해야 가장 효율적으로 line 명령을 처리할까...

영알못들을 위한 해석

city 갯수를 입력하고 city 위치를 입력함

그 이후 road 명령으로 city들을 state로 이어주고

line 명령을 통해 그 line에 닿는 모든 state와 그 구성 city들을 체크해야 함

어렵다 어려워

이게 한달 전 쯤? 푼 문제인데 아직도 타임아웃뜸 ㅠㅠ

[ㅎ흑왕ㅇ(whiteprince)]

오디소 제출하는고야?

[whatugonnado(sibal214)]

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=356&page=show_problem&problem=2731

[whatugonnado(sibal214)]

acm icpc 서울 지역예선 2009년도 문제

[ㅎ흑왕ㅇ(whiteprince)]

충돌검출 + 공간분할 하면 안댈까

[야이미친(121.44)]

City=[x,y], road=[city1,city2], state=[road1,road2,...].. 이케되면 라인은 로드 집합 쭉 돌면서 y축 지나는거 찾고, 찾은거로 state의 부분집합 찾으면 되는거 같은디... 이상 똥싸면서 잠시 두뇌운동

[whatugonnado(sibal214)]

문제 풀어보면 알겠지만 city의 x값은 필요가 전혀 없어서 y값과 state의 인덱스만 가지고 있고, state는 city의 인댁스와 자기가 몇개의 city들을 가지고 있는지를 가지고, road는 입력할 때 마다 city와 state 값에 영향을 주고 line명령때 state만 참조해서 출력하게 했음

[야이미친(121.44)]

나라면 철저히 집합개념으로 푼다

[ㅎ흑왕ㅇ(whiteprince)]

국가단위로 만들어서 바운딩 박스 만들고 뭐 그런거? ㅎㅎ

[야이미친(121.44)]

즉, 라인집합, 시티집합, 스테이트집합. 경우에 따라 순서있는 집합

[whatugonnado(sibal214)]

왠지 타임아웃 뜰거 같은데 한번 내일 그걸로 풀어보고 결과 올려봄

[야이미친(121.44)]

아니 그게 왜 타임아웃이 떠? ㅋㅋㅋ 라인이 통과하는 모든 시티를 구하고 그 시티가 속한 모든 스테이트를 구한 후 다시 각각의 스테이트 시티수를 더하면 되는건데

[야이미친(121.44)]

이상 똥눈후 씯고 물기 닦으며 한 추가 두뇌운동

[whatugonnado(sibal214)]

내가 댓글로 안적은게 있는데 내 state에는 city_Y_min , city_Y_max 값을 저장해서 그 사이에 line값이 들어가면 들어간 state 수를 더하게끔 만들어놨음

[whatugonnado(sibal214)]

난 state만 돌면서 max, min 사이에 line값이 있으면 state와 거기에 속해있는 city값을 더하는 식으로만 계산해도 타임아웃이 뜨는데

[whatugonnado(sibal214)]

넌 라인 참고하고 라인에 포함된 city값 갔다가 다시 state까지 가는데 오래 안걸린다는 얘기임?

[whatugonnado(sibal214)]

물론 내가 말한 방법으로는 입력할때 연산이 좀 복잡해서 입력단계에서 타임아웃 뜨는거 같긴 하지만.. 암튼 그방법은 입력에선 아무것도 문제될게 없으니 더 빠를수도 있겠다 내일 해볼겡 ㅇㅅㅇ;

[야이미친(121.44)]

얌마 컴퓨터가 단순 덧셈이나 숫자비교는 졸라 빠른건 혹시 아냐? ㅋㅋㅋ 걍 문제를 니 머리가 어떤식으로 푸는지 생각해보고 그대로 풀어

[whatugonnado(sibal214)]

내가 그걸 모를까봐?ㅋㅋㅋㅋ