Bedan Contest #03 - C - Đường tròn

Điểm: 1600 (thành phần)

Thời gian: 2.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

flo

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python

This is a geometry problem since I love geometry so much.

Cho $n$ điểm phân biệt trên mặt phẳng tọa độ Descartes, điểm thứ $i$ có tọa độ là $(x_i, y_i)$ . Với mỗi cặp điểm, vẽ một đường tròn có đường kính là đoạn thẳng nối cặp điểm đó lại với nhau. Khi đó, ta sẽ có tổng cộng $\frac{n\times (n-1)}{2}$ đường tròn khác nhau.

Nhiệm vụ của bạn là với mỗi điểm trong $n$ điểm trên, bạn hãy xác định số lượng đường tròn mà nó nằm trên với điều kiện nó không trùng với đầu mút của đường kính của những đường tròn đó. Chúc bạn may mắn nhé!

Input, Output and Scoring

Input

Số nguyên dương $n$ $(1 \le n \le 2000)$ .
$n$ dòng tiếp theo, dòng thứ $i$ chứa tọa độ điểm thứ $i$ là $(x_i, y_i)$ $(|x_i|, |y_i| \le 10^9)$ .

Output

In ra $n$ số nguyên không âm, số thứ $i$ là số lượng đường tròn điểm thứ $i$ nằm trên mà điểm đó không trùng với đầu mút của đường kính của những đường tròn đó.

Scoring

Subtask $1$ $(20\%)$ : $1 \le n \le 200$ .
Subtask $2$ $(80\%)$ : Không giới hạn gì thêm.

Test 1

Input

Output

1 0 1 0

Note

Điểm $(3, 1)$ nằm trên đường tròn có đường kính là đoạn thẳng nối $2$ điểm $(3, 6)$ và $(10, 1)$ .
Điểm $(5, 2)$ nằm trên đường tròn có đường kính là đoạn thẳng nối $2$ điểm $(3, 1)$ và $(3, 6)$ .

Test 2

Input

Output

1 1 1 1

Note

Điểm $(1, 1)$ và $(2, 2)$ nằm trên đường tròn có đường kính là đoạn thẳng nối $2$ điểm $(1, 2)$ và $(2, 1)$ .
Điểm $(1, 2)$ và $(2, 1)$ nằm trên đường tròn có đường kính là đoạn thẳng nối $2$ điểm $(1, 1)$ và $(2, 2)$ .

Bình luận

Không có bình luận nào.