APIO 2010- 신호 > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


2482 : 신호

제한시간
2000 ms   
메모리제한
0 MB   
해결횟수
6 회   
시도횟수
13 회   

문제

어느 통신회사가 GSM(이동전화) 통신망을 개발하고 있다. 이 통신망은 도시에 있는 n개의 집에서 사용이 가능하도록 하려고 한다. 그러나 제한된 예산 때문에 이 회사는 단 하나의 안테나만 세울 수 있다.

 

안테나는 n개의 집들 중 3개를 선택하여, 이 집들로 만들어지는 원의 중심에 세운다. 이 경우, 이 원의 내부와 경계에 있는 모든 집들은 이 안테나로부터 신호를 받을 수 있다.

 

이 회사는 무작위로 세 곳의 집을 선택하려고 계획하고 있고 이때 신호를 받을 수 있는 집들의 수를 알기 위하여, 가능한 모든 세 집들에 대한 안테나 위치에 대해서 신호를 받을 수 있는 집들의 수의 평균을 구하고자 한다.

 

예를 들어, 아래의 그림과 같이 A,B,C,D 네 개의 집들이 있다고 하자.

 

 

 

위 그림에서 ABC 혹은 BCD의 집들을 선택하면, 이 경우의 안테나는 모든 집들에게 신호를 보낼 수 있다. 그러나 ACD 혹은 ABD를 선택하는 경우에는 하나의 집에서는 신호를 받지 못한다.

 

그러므로 신호를 받을 수 있는 집들의 수의 평균은 (4+4+3+3)/4 = 3.5 이다.

 

여러분이 할 일은 집들의 위치가 주어질 때, 신호를 받을 수 있는 집들의 수의 평균을 구하는 것이다. 집들의 위치는 2차원 좌표계에서 정수좌표로 주어진다. 어떠한 세 집도 하나의 직선상에 존재하지 않으며, 어떠한 네 집도 하나의 원의 경계(원주)위에 존재하지 않는다.


입력형식

첫 번째 줄에 전체 집들의 수를 나타내는 하나의 양의 정수 n이 주어진다.

그 다음의 n개의 각 줄에 집들의 위치가 주어진다.

i ∈ {1, 2, ..., n}에 대하여, 집 i의 위치 좌표를 나타내는 두 개의 정수 xi와 yi는 i+1 번째 줄에 공백을 사이에 두고 주어진다.


출력형식

안테나의 신호가 도달 가능한 집들의 수의 평균을 소수점 셋째 자리에서 반올림 한 값을 출력한다.

 

[제약조건] 

3≤n≤1,500 이다. 

모든 테스트 경우, i∈ {1, 2, ..., n}에 대하여 집 i의 좌표 ( xi, yi )는 모두 정수로서 -1,000,000 이상 1,000,000 이하의 정수다. 

어떠한 세 집도 하나의 직선상에 존재하지 않으며, 어떠한 네 집도 하나의 원의 경계(원주)위에 존재하지 않는다.


입력 예

복사하기

4
0 2
4 4
0 0 
2 0

출력 예

복사하기

3.50

출처

APIO 2010

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP