CodeUp[Q_2629] : 광역시

1. 문제

https://codeup.kr/problem.php?id=2629

광역시

[출처 : 코드업(https://codeup.kr/)]

이번에는 (0,0)을 기준으로 원을 이루면서 확장시키면서

최초로 인구수가 100만이 넘을때의 r(반지름)을 구하는 문제입니다.

 

 

2. 풀이방법

STEP 1. 주어진 좌표들을 (0,0)기준으로 거리 순으로 정렬한다.

STEP 2. 가장 가까운 거리의 점부터 인구수를 더한다.

 

 

3. 해답

#include <stdio.h>
#include <math.h>

int arr[10000][2] = { 0, };

void SWAP(int* a, int* b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void my_qsort(int left, int right) {
	int pl = left;
	int pr = right;
	int x = arr[(pl + pr) / 2][0];

	do {
		while (arr[pl][0] < x) pl++;
		while (arr[pr][0] > x) pr--;
		if (pl <= pr) {
			SWAP(&arr[pl][0], &arr[pr][0]);
			SWAP(&arr[pl][1], &arr[pr][1]);
			pl++;
			pr--;
		}
	} while (pl <= pr);
	if (left < pr) my_qsort(left, pr);
	if (pl < right) my_qsort(pl, right);
}

int main()
{
	int n, p;
	int x, y;

	scanf("%d %d", &n, &p);
	p = 1000000 - p; // 100만명까지 남은 인구수

	for (int i = 0; i < n; i++) {
		scanf("%d %d %d", &x, &y, &arr[i][1]);

		arr[i][0] = x * x + y * y; // (0,0) 과 떨어진 거리 = r^2
	}

	my_qsort(0, n - 1); // 거리 순으로 정렬

	for (int i = 0; i < n; i++) {
		p -= arr[i][1]; // 가장 가까운 도시부터 더하기
		if (p <= 0) {
			// 100만명이 넘어가면
			printf("%.3lf", sqrt(arr[i][0]));
			return 0;
		}
	}

	printf("-1");

	return 0;
}