시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 77 | 18 | 14 | 21.875% |
플라위 : 반가워! 내 이름은 플라위, 노란 꽃 플라위야!! 너 이 지하세계는 처음인가 보구나, 그렇지? 이런, 정말 정신 없겠네. 이곳이 어떤 곳인지 누군가 알려줘야겠는데! 작고 힘없는 나라도 알려줘야겠네. 준비됐니? 간다!
플라위 : 하트 모양이 보이지? 저게 네 영혼이야. 네 존재의 정수지! 네 영혼은 약하지만, LV를 많이 올리면 강해질 수 있어. LV가 뭐냐고? 바로, LOVE지, 물론! LOVE가 좀 필요한 것 같은데, 그렇지?
플라위 : 걱정하지 마, 내가 좀 나눠줄게! 작고 하얀... “친절 알갱이”로 서로 나누지. 움직여! 친절을 최대한 많이 받는 거야!
플라위는 총 N개의 친절 알갱이를 뿌렸다. 이 알갱이들은 모두 1의 속도로 일직선으로 움직인다. 한편, 당신의 영혼도 임의의 방향으로 최대 1의 속도로 움직일 수 있다. 당신은 1, 0.314 등의 임의의 속도로 움직일 수 있으며, 가만히 있을 수도 있다. 하지만 영혼은 특정 직사각형 영역 밖으로 나갈 수 없다. 당신의 영혼은 처음에 (0, 0) 위치에 있으며, [-XM, -YM] ~ [XM, YM] 범위 안에서만 움직일 수 있다.
각각의 친절 알갱이는 당신의 영혼과 닿으면 사라진다. 따라서 당신은 최대 N개의 친절 알갱이를 모을 수 있다. 친절 알갱이의 정보가 주어질 때, 당신이 최대 몇 개의 친절 알갱이를 모을 수 있는지 구하는 프로그램을 작성하라. 단, 당신의 영혼과 친절 알갱이는 점으로 간주한다.
첫 번째 줄에는 친절 알갱이의 수 N(1 ≤ N ≤ 18), 영혼이 도달할 수 있는 범위를 나타내는 두 정수 XM, YM (1 ≤ XM, YM ≤ 500)이 주어진다. 두 번째 줄부터 N개의 줄에는 각각의 친절 알갱이의 정보에 해당하는 4개의 정수 Xst, Yst, Xto, Yto(-1,000 ≤ Xst, Yst, Xto, Yto ≤ 1,000)가 주어진다. 친절 알갱이의 처음 위치는 (Xst, Yst)이며, 이 알갱이는 (Xto, Yto)를 향해 일직선으로 움직인다. 친절 알갱이는 (Xto, Yto)를 지난 이후에도 계속 움직인다. (Xst, Yst)와 (Xto, Yto)는 서로 다른 점이며, 출발점이 원점으로 들어오는 경우는 없다.
첫 번째 줄에 당신이 모을 수 있는 친절 알갱이의 수의 최댓값을 출력한다.
5 10 8 -12 24 0 0 -8 28 0 0 0 30 0 0 8 28 0 0 12 24 0 0
5
4 93 93 93 93 93 -93 93 -93 -93 -93 -93 -93 -93 93 -93 93 93 93
2
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2016 D번