QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

#21223. 소의 브리지 대결

Statistics

Farmer John의 소 $N$마리 ($4 \le N \le 1,000$)가 주 목초지에서 차분히 기다립니다. 소 $i$는 정수 좌표 ($X_{i}$, $Y_{i}$)에 있고 $-1,000,000,000 \le X_{i} \le 1,000,000,000; -1,000,000,000 \le Y_{i} \le 1,000,000,000$입니다.

소들은 새로 좋아하게 된 카드 게임 브리지를 하려고 네 마리씩 모이려 합니다. 중요한 조건은 평면에 점 $X$ (네 소의 어떤 위치와도 다름)가 있어서 어느 소든 $X$를 중심으로 $180$도 회전하면 같은 그룹의 다른 소 위치가 되는 것입니다. 이 조건을 만족할 때에만 그룹을 만들 수 있습니다.

유효한 브리지 그룹을 만들 수 있는 네 소의 집합 수를 구하세요.

예를 들어 여덟 소가 다음 여덟 점에 있다고 합시다.

                  |
                 f*
                  |             a = (-3, 1)    e = (-1, 1)
           b*     |             b = (-2, 2)    f = ( 0, 3)
        a      e  |             c = (-3, 0)    g = ( 2, 0)
         *     *  |             d = (-2, 0)    h = ( 3, 0)
         c  d     |     g  h
---------*--*-----+-----*--*---------
                  |

세 유효한 집합은 $\{a,b,e,d\}$ (회전 중심 $(-2,1)$), $\{b,c,e,f\}$ (중심 $(-1.5,1.5)$), $\{c,d,g,h\}$ (중심 $(0,0)$)입니다.

주어진 위치는 모두 서로 다르고 특정 순서로 주어지지 않습니다. 답은 부호 있는 32비트 정수에 들어갑니다.

입력

  • 줄 1: 정수 $N$ 하나.
  • 줄 $2 \ldots N+1$: 줄 $i+1$에는 공백으로 구분한 두 정수 $X_{i}$, $Y_{i}$가 있습니다.

출력

  • 줄 1: 유효한 브리지 그룹을 이루는 네 소의 집합 수인 정수 하나.

예제

입력 1

8
-3 0
-2 0
-1 1
0 3
2 0
-3 1
3 0
-2 2

출력 1

3

문제 출제: Richard Ho, 2007

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.