고양멍멍이

[문제링크]

0. 주어진 문자로 만들수 있는 모든 순열 중, 조건을 만족하는 갯수를 구하는 문제

  - 조건 1. 인접한 문자는 달라야 한다

  - 조건 2. 최종 결과가 달라야 한다 (a 2개로 aa', a'a을 만들수 있지만, 둘은 같은것으로 취급한다)

1. 순열의 i번째 자리를 정할 때 이전 문자정보를 참고해 다른 문자만 사용한다면, 조건 1번은 해결할 수 있다

  - 0번째 자리에서 참조할 값으로는 입력값(알파벳)이 아닌 아무 문자나 주면 된다

2. 조건 2번의 경우, 여러번 등장하는 같은 문자를 다른 문자로서 사용하기 때문에 발생한다.

  - 즉, i번째 자리에 한번 a 문자를 사용했다면 a가 또 등장해도 사용하지 않으면 해결할 수 있다

3. 이를 위해, 한번 사용한 문자의 정보를 저장해두어 중복 사용하는것을 막았다 (bitmask)

4. 2/3번에서 걸러지지 않고 끝까지 완료된 순열만 count해주면 된다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		s = br.readLine().toCharArray();
		isC=new boolean[s.length];
		cntLuck=0;
		lucky(0, ' ');
		System.out.println(cntLuck);
	}
	
	static char[] s;
	static boolean[] isC;
	static int cntLuck;
	
	static void lucky(int cnt, char prev) {
		if(cnt==s.length) {
			cntLuck++;
			return;
		}
		int bitMask=0;
		for (int i = 0; i < s.length; i++) {
			if(!isC[i] && s[i]!=prev && ( (bitMask&1<<(s[i]-'a')) == 0)) {
				//not used + not same with prev
				isC[i]=true;
				bitMask|=1<<(s[i]-'a');
				lucky(cnt+1, s[i]);
				isC[i]=false;
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. C++ 등 일부 언어에서 내장 라이브러리로 제공하는 next permutation 문제

  - 알파벳 순서대로 만들어진 조합의 다음 모습 구하기

1. next permutation을 구하는 방법은?

• 뒤에서부터 탐색해, 증가하지 않는 첫 부분의 위치를 구한다
  • 126543 을 예시로 하면, 3-4-5-6-2-1 이므로 2가 구하려는 위치이다
• 다시 뒤에서부터 탐색해, 2보다 큰 수들 중 처음 나오는 수의 위치를 구한다
  • 3-4-5-6-2-1 순서이므로 3이 2보다 큰 수이면서 가장 처음 나오는 수이다
• 1/2에서 구한 두 위치의 수를 바꾼다
  • 126543은 2/3이 바뀌며 136542가 된다
• 1번에서 구한 위치 뒤쪽의 수들을 정렬한다
  • 2번째 수였으므로 3~끝까지 정렬한다
  • 136542에서 132456이 된다

2. 실제 풀이 방법

• 앞부분 - 뒷부분 2개의 stringbuilder를 둔다
• 뒤에서부터 탐색해, 증가하지 않는 첫 위치(이하 A위치)를 구하며 큐에 넣는다
• 해당 위치 앞은 변하지 않을 것이니, 앞부분 builder에 넣는다
• 큐에 들어가 있는 부분은 오름차순으로 진행하며 차례대로 넣는 뒷부분이니, 그대로 꺼내도 정렬되어 있다
• 큐에서 하나씩 꺼내면서 뒷부분 builder에 넣되, A위치 수보다 커질때 한번 따로 처리해야한다
• 커지는 순간 큐에서 꺼낸 수는 앞부분 builder에, A위치의 수는 뒷부분 builder에 넣는다 (swap의 역할)
• 큐의 나머지는 다 뒷부분에 넣는다

• 최종적으로 합치면 종료

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			StringBuilder sb = new StringBuilder();
			StringBuilder sb_back = new StringBuilder();
			char[] str = br.readLine().toCharArray();
			
			Queue<Character> qu = new LinkedList<>();
			int len = str.length-1;
			while(len>0 && str[len-1] >= str[len]) {
				qu.add(str[len]);
				len--;
			}
			if(len==0) {
				//다음 단어가 없다
				System.out.println(str);
			}
			else {
				qu.add(str[len]);
				len--;
				
				//정상인 앞부분 넣기
				for (int i = 0; i < len; i++) {
					sb.append(str[i]);
				}
                
				//바뀔 위치 탐색
				char temp=' ';
				while(qu.peek() <= str[len]) {
					temp=qu.poll();
					sb_back.append(temp);
				}
                
				//바꾼다
				sb.append(qu.poll());
				sb_back.append(str[len]);
                
				//나머지 넣기
				while(!qu.isEmpty()) {
					sb_back.append(qu.poll());
				}

				System.out.print(sb);
				System.out.println(sb_back);
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 국경선을 여는, 연합을 구한 다음, 연합 국가들의 인구를 공통 배분한다

  - 더이상 연합이 형성되지 않을때까지 반복

1. L 이상 R 이하일때 진행하는 DFS로 연합과 그 인구를 구한다

  - 인구는 DFS 결과로 반환, 연합은 tempMap 배열에 idx를 작성한다

2. 연합이 형성되지 않았다면, 즉 DFS가 호출된 횟수가 국가의 횟수와 같다면 종료 후 소요된 day 출력

3. 연합이 형성되었다면, 인구수를 골고루 분배해 갱신한다 (소숫점은 버리므로 int 간 나눗셈)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		 n = pint(st.nextToken());
		L = pint(st.nextToken());
		R = pint(st.nextToken());
		map = new int[n][n];
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				map[i][j]=pint(st.nextToken());
			}
		}
		
		int day=0;
		while(true) {
			union = new ArrayList<>();
			tempMap=new int[n][n];
			
			int cnt=1;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if(tempMap[i][j]==0) {
						//union을 찾아서,
						//전체 합계와 나라 갯수를 저장한다
						num=0;
						union.add(new int[] {find(i,j,cnt++), num});
					}
				}
			}
			
			if(cnt==n*n+1)break;//union이 없으면 끝, 탈출한다
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					//찾은 union정보를 바탕으로 각 나라별 새 인구를 채워넣는다
					map[i][j]=union.get(tempMap[i][j]-1)[0] / union.get(tempMap[i][j]-1)[1];
				}
			}
			day++;
			
		}
		System.out.println(day);
		
	}
	static int n,L,R, num;
	static ArrayList<int[]> union;
	static int[][]map;
	static int[][]tempMap;
	
	static int find(int x, int y, int cnt) {
		tempMap[x][y]=cnt;
		num++;
		int popul=map[x][y];
		if(x>0 && tempMap[x-1][y]==0
				&& Math.abs(map[x-1][y]-map[x][y])>=L
				&& Math.abs(map[x-1][y]-map[x][y])<=R) {
			popul+=find(x-1,y,cnt);
		}
		if(x<n-1 && tempMap[x+1][y]==0
				&& Math.abs(map[x+1][y]-map[x][y])>=L
				&& Math.abs(map[x+1][y]-map[x][y])<=R) {
			popul+=find(x+1,y,cnt);
		}
		if(y>0 && tempMap[x][y-1]==0
				&& Math.abs(map[x][y-1]-map[x][y])>=L
				&& Math.abs(map[x][y-1]-map[x][y])<=R) {
			popul+=find(x,y-1,cnt);
		}
		if(y<n-1 && tempMap[x][y+1]==0
				&& Math.abs(map[x][y+1]-map[x][y])>=L
				&& Math.abs(map[x][y+1]-map[x][y])<=R) {
			popul+=find(x,y+1,cnt);
		}
		
		return popul;
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 단순한 구현 문제

  - 2-b 수행하기 전 2-c,d먼저 조건 체크/수행해야한다

1. 현재 위치를 청소하며 clean 수치를 1씩 증가시킨다

2. 2-c,d 조건 체크를 위해 4방향 탐색

3. 4방향 다 벽/청소가 끝났다면 현 위치의 뒤를 확인하여 벽이라면 종료한다 (2-d)

4. 벽이 아니라면, 뒤로 물러난다 (2-c)

5. 왼쪽에 빈공간이 있다면, 회전 후 1칸 진행한다 (2-a)

4. 없다면, 회전한다 (2-b)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	
	static int[][]left= {
			{0,-1},//북쪽 기준 왼쪽
			{-1,0},//동쪽 기준 왼쪽
			{0,1},//남쪽기준
			{1,0}//서쪽기준
	};
	static int[][]back= {
			{1,0},//북쪽 기준 뒤쪽
			{0,-1},//동쪽 기준 뒤쪽
			{-1,0},//남쪽 기준 뒤쪽
			{0,1}//서쪽 기준 뒤쪽
	};
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		st = new StringTokenizer(br.readLine(), " ");
		int r = pint(st.nextToken());
		int c = pint(st.nextToken());
		int d = pint(st.nextToken());
		
		int[][]map = new int[n][m];
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				map[i][j]=pint(st.nextToken());
			}
		}
		
		int clean=0;
		while(true) {
			//1
			if(map[r][c]==0) {
				map[r][c]=2;
				clean++;
			}
			//2-c
			//2-d
			boolean isDone=true;
			for (int i = 0; i < 4; i++) {
				if(map[ r+left[i][0] ][ c+left[i][1] ]==0) {
					isDone=false;
				}
			}
			if(isDone) {//4방에 0이 없으면
				if(map[r+back[d][0]][c+back[d][1]]==1) {
					//2-D, 뒤가 벽
					break;
				}
				else {
					//2-C, 물러남
					r+=back[d][0];
					c+=back[d][1];
					continue;
				}
			}
			
			//2-a
			//왼쪽에 청소 안했으면
			if(map[r+left[d][0]][c+left[d][1]]==0) {
				r+=left[d][0];
				c+=left[d][1];
				d=(d+4-1)%4;
			}
			//2-b
			else {
				d=(d+4-1)%4;
			}
		}
		System.out.println(clean);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. N세대 드래곤 커브란? N-1세대 드래곤 커브를 끝 점 기준 90도 회전시켜 N-1세대의 끝 점에 붙인 것

  - 한 세대마다 2배씩 증가하지만, 세대가 최대 10이므로 최대 pow(2,10), 1024개의 지점으로 구성된다

1. N세대 드래곤 커브를 만들기 위해선?

  - N-1세대의 끝 점에서 시작해, N-1세대 커브의 구성을 역순으로 90도 회전시켜서 적용한다

  - 예를들어, 위 2세대 커브는 →↑←↑ 순서로 이루어져 0, -2 지점에서 종료되었다.

  - 3세대 커브를 만들려면 0, -2 지점에서 2세대 커브의 역순인 ↑←↑→ 이동을, 90도 회전시켜 ←↓←↑ 순서로 진행하면 된다

  - 이는 문제 예시를 통해 확인 가능하다

2. 해당 과정을 위해 N세대까지 거쳐온 기록을 Arraylist로 저장하고, 이를 역순으로 탐색하며 끝점을 이동시킨다

3. 끝점은 분명한 경로를 가지고 움직이지만, 문제의 요구사항은 0<=x,y<=100 인 (x,y) 좌표에 대해서 정사각형을 구하는 것이므로, 끝 점이 방문한 좌표만 기록한다

4. 모든 커브가 그려진 후, 0~100의 좌표들에 대해서 사각형 조건 충족 여부를 검사, 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	
	static int[][] dir= {
			{0,1},
			{-1,0},
			{0,-1},
			{1,0}
	};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int cntSquare=0;
		boolean[][] map = new boolean[101][101];
		
		int N = pint(br.readLine());
		for (int i = 0; i < N; i++) {

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int y = pint(st.nextToken());
			int x = pint(st.nextToken());
			int d = pint(st.nextToken());
			int g = pint(st.nextToken());
			
			if(inBox(x,y)) {
				map[x][y]=true;
			}
			x+=dir[d][0];
			y+=dir[d][1];
			if(inBox(x,y)) {
				map[x][y]=true;
			}
			//curve의 경로 저장
			List<Integer>curve = new ArrayList<>();
			curve.add(d);
			
			for (int j = 0; j < g; j++) {
				for (int j2 = curve.size()-1; j2 >= 0; j2--) {
					//curve를 역순으로 탐색
					int curDir = curve.get(j2);
					//90도 회전
					int nextDir=(curDir+1)%4;
					//끝 점 이동 적용
					x+=dir[nextDir][0];
					y+=dir[nextDir][1];
					if(inBox(x,y)) {
						map[x][y]=true;
					}
					curve.add(nextDir);
				}
			}
			
		}
		
		//조건을 만족하는 사각형의 갯수 찾기
		for (int i = 0; i <100; i++) {
			for (int j = 0; j < 100; j++) {
				if(map[i][j] && map[i][j+1] && map[i+1][j] && map[i+1][j+1]) {
					cntSquare++;
				}
			}
		}
		System.out.println(cntSquare);
	}
	
	static boolean inBox(int x, int y) {
		if(x>=0 && x<=100 && y>=0 && y<=100)return true;
		return false;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 기초적인 MST 문제 (MST란?)

1. PRIM 알고리즘 사용, 최소 거리로 갈수있는 & 미방문한 노드 순서로 방문한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = pint(br.readLine());
		int M = pint(br.readLine());
		
		graph = new LinkedList<>();
		for (int i = 0; i <= N; i++) {
			graph.add(new LinkedList<>());
		}
		
		for (int i = 1; i <= M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int fst = pint(st.nextToken());
			int snd = pint(st.nextToken());
			int cost = pint(st.nextToken());
			
			graph.get(fst).add(new int[] {snd, cost});
			graph.get(snd).add(new int[] {fst, cost});
		}
		
		int totalCost=0;
		int start=1;//아무거나
		
		boolean[] isVisit=new boolean[N+1];//방문체크
		int[] cost = new int[N+1]; // 0번 PC는 없다
		Arrays.fill(cost, Integer.MAX_VALUE);
		cost[start]=0;//시작 cost 초기화
		
		for (int i = 0; i < N; i++) {
			
			int min=Integer.MAX_VALUE;
			int minNode=0;
			for (int j = 1; j <= N; j++) {
				if(!isVisit[j] && cost[j]<min) {
					min=cost[j];
					minNode=j;
				}
			}
			//가장 짧은거 연결
			isVisit[minNode]=true;
			totalCost+=min;
			
			//minNode 에서 연결되있는거 갱신
			int len = graph.get(minNode).size();
			for (int j = 0; j < len; j++) {
				int[] adjNode = graph.get(minNode).get(j);
				if(!isVisit[adjNode[0]]) {
					//방문한적 없다면
					cost[adjNode[0]] = Math.min(cost[adjNode[0]], adjNode[1]);
				}
			}
		}
		System.out.println(totalCost);
		
	}
	static LinkedList<LinkedList<int[]>>graph;
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 집 사이의 연결을 유지하며 길을 제거하고, 최소 비용의 길들을 사용해 전체를 연결하기 == 최소 신장 트리(MST)

1. 최소 신장 트리를 구하면 최소 거리의 길들로 모든 마을을 연결할 수 있다

2. 완성된 MST의 간선들 중 하나를 제거하면 2개의 tree가 생성된다

  - 마을을 2개로 분리할 수 있다

3. 길의 유지비의 합은 항상 최소를 유지해야하므로, MST를 이루는 간선들 중 가중치가 가장 큰 간선 하나를 제거하면 마을을 분리하면서 비용을 최소로 만들 수 있다

  - Kruskal의 경우, 간선을 기준으로 최소 간선부터 고려하므로, 마지막에 선택할 간선을 선택하지 않아도 된다

  - N개의 집이 있을때, N-1개가 아닌 N-2개만 선택하는 것

<Kruskal 사용>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());

		//간선 리스트..대신 크기가 주어지니 배열 사용
		edge[] e = new edge[m];
		for (int i = 0; i < m; i++) {
			e[i]=new edge();
			st = new StringTokenizer(br.readLine(), " ");
			
			e[i].n1=pint(st.nextToken());
			e[i].n2=pint(st.nextToken());
			e[i].cost=pint(st.nextToken());
		}
		
		Arrays.sort(e);
		
		init(n);
		
		int cnt=0, i=0;//현재 선택한 edge의 갯수
		int totalCost=0;//누적 전체cost
		while(true) {
			//union이 정상적으로 수행 됬다면
			if(union(e[i].n1, e[i].n2)) {
				//cnt, cost 반영
				cnt++;
				totalCost+=e[i].cost;
			}
			if(cnt==n-1)break;
			i++;
		}
		//최소 cost의 2개의 마을로 분할하는 법 = MST에서 가장 cost가 큰 edge 하나 자르기
		System.out.println(totalCost-e[i].cost);
	}

	//분리집합
	static int[]parents;
	static void init(int n) {
		parents=new int[n+1];
		for (int i = 0; i <= n; i++) {
			parents[i]=i;
		}
	}
	static int find(int n) {
		if(parents[n]==n)return n;
		return parents[n]=find(parents[n]);
	}
	static boolean union(int n1, int n2) {
		int p1=find(n1);
		int p2=find(n2);
		
		if(p1==p2)return false;
		parents[p1]=p2;
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	//간선 객체
	static class edge implements Comparable<edge>{
		int n1;
		int n2;
		int cost;
		@Override
		public int compareTo(edge e) {
			return this.cost-e.cost;
		}		
	}
}

<Prim 사용>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());

		ArrayList<ArrayList<int[]>>graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<>());
		}
		//그래프 입력
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken());
			int y = pint(st.nextToken());
			int cost = pint(st.nextToken());

			graph.get(x).add(new int[] {y,cost});
			graph.get(y).add(new int[] {x,cost});
		}
		
		int totalCost=0, cnt=0, max=-1;
		//전처리
		boolean[] isV = new boolean[n+1];
		PriorityQueue<int[]>pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[1]-o2[1];
			}
		});
		for (int i = 1; i <= n; i++) {
			pq.offer(new int[] {i,Integer.MAX_VALUE});
		}
		//임의의 시작 노드 설정
		pq.offer(new int[] {1,0});
		
		while(cnt!=n) {
			int[] curNode = pq.poll();

			if(isV[curNode[0]])continue;//이미 방문한 node면
			
			isV[curNode[0]]=true;
			totalCost+=curNode[1];
			if(max<curNode[1])max=curNode[1];
			cnt++;
			
			for (int i = 0; i < graph.get(curNode[0]).size(); i++) {
				int[] next = graph.get(curNode[0]).get(i);
				if(!isV[next[0]]) {
					pq.offer(next);
				}
			}
			
		}
		System.out.println(totalCost-max);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 모든 경우의 수에 대해 계산하는 브루트-포스 방식

1. 벡터는 두 점 A, B가 있을때 A-B / B-A 같은 식으로 만들 수 있다

  - 한 점은 +, 한 점은 - 하게 된다

2. 즉, 2N개의 점으로 N개의 벡터를 만들었을때 그 벡터들의 합은 N개의 점을 +, 나머지 N개는 - 한 값이다

3. 점이 최대 20개인데, 20개 중 10개를 뽑는 조합의 경우의 수 ₂₀C₁₀은 184756으로 산술 시간안에 충분히 해결 가능하다

4. 10개의 점을 선택해 더하고, 선택되지 않은 10개의 점을 빼는 식으로도 결과를 구할 수 있지만,

  - 산술 연산의 횟수를 줄이기 위해 모든 수를 더해두고, 10개의 점을 선택해 2번씩 빼준다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			N = pint(br.readLine());
			isC=new boolean[N];
			point= new int[N][2];
			int sumx=0,sumy=0;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				point[i][0]=pint(st.nextToken());
				point[i][1]= pint(st.nextToken());
				sumx+=point[i][0];
				sumy+=point[i][1];
			}
			
			ans=Double.MAX_VALUE;
			rec(0,0, sumx, sumy);
			sb.append(ans).append("\n");
		}
		System.out.println(sb);
		
	}
	static double ans;
	static int N;
	static boolean[] isC;
	static int[][]point;
	
	static void rec(int cnt, int prev, int x, int y) {
		if(cnt==N/2) {
			ans = Math.min(ans, Math.sqrt((double)x*x + (double)y*y) );
			return;
		}
		for (int i = prev; i < N; i++)
			rec(cnt+1, i+1, x-2*point[i][0], y-2*point[i][1]);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}