팀 배틀
면접 대비시간 제한1초메모리 제한1024 MB
정수 실력을 가진 두 팀 A, B가 무작위로 짝지어 경기할 때, 각 경기에서 이긴 쪽이 실력 차의 제곱만큼 점수를 얻는다. (A 점수) - (B 점수)의 기댓값을 구한다.
문제
n(1 ≤ n ≤ 50,000)명의 사람으로 이루어진 두 팀 A, B가 팀 배틀을 한다. 팀 배틀은 n명의 사람이 상대 팀의 사람과 1:1로 실력을 겨루는 방식으로 진행된다. 각 사람의 대전 상대는 무작위로 정해지며, 가능한 모든 대진은 같은 확률로 나타난다. 예를 들어 두 팀이 (A1, A2), (B1, B2)로 이루어져 있다면 가능한 대진은 (A1:B1, A2:B2)와 (A1:B2, A2:B1) 두 가지이고, 각각 50%의 확률로 나타난다.
각 사람의 실력은 음이 아닌 정수로 주어진다. 실력은 절대적이므로 실력을 나타내는 정수가 큰 쪽이 이긴다. 이긴 사람은 두 실력 차의 제곱만큼 점수를 받고, 진 사람은 0점을 받는다. 두 사람의 실력이 같으면 무승부이며 양쪽 모두 0점을 받는다. 각 팀의 점수는 그 팀의 팀원들이 받은 점수의 합이다.
각 팀원의 실력을 나타내는 정수가 주어졌을 때, [(A팀의 점수)-(B팀의 점수)]의 기댓값(평균)을 구하는 프로그램을 작성하시오.
예를 들어 A팀의 실력이 (3, 7), B팀의 실력이 (1, 5)라 하자. 가능한 대진은 (3:1, 7:5)와 (3:5, 7:1)이다. 앞의 경우 A팀은 (3 - 1)2 + (7 - 5)2 = 8점, B팀은 0점을 받으므로 (A팀의 점수) - (B팀의 점수) = 8이다. 뒤의 경우 A팀은 (7 - 1)2 = 36점, B팀은 (5 - 3)2 = 4점을 받으므로 (A팀의 점수) - (B팀의 점수) = 32이다. 따라서 평균은 (8 + 32) / 2 = 20점이다.
입력
첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 A팀 팀원의 실력을 나타내는 정수가, 그 다음 n개의 줄에는 B팀 팀원의 실력을 나타내는 정수가 주어진다. 실력을 나타내는 정수는 50,000 이하의 음이 아닌 정수이다.
출력
첫째 줄에 기댓값을 출력한다. 절대 오차 또는 상대 오차는 10-6까지 허용한다.