Màu điểm (Đề 2)


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type
Allowed languages
C++

Cho \(n\) điểm trong mặt phẳng đôi một không trùng nhau, mỗi điểm có thể coi là một đối tượng với các thuộc tính sau:

  • Hoành độ, số nguyên.
  • Tung độ, số nguyên.
  • Màu, số tự nhiên. Biết rằng có \(9\) màu kí hiệu từ \(1\) - \(9\). Thiết kế các lớp phù hợp, nhập vào \(n\) điểm rồi thực hiện những công việc dưới đây:

\(a)\) Tìm các màu xuất hiện với số lần nhiều nhất.

\(b)\) Đếm số đoạn thẳng khác màu có đầu mút là hai điểm khác màu.

\(c)\) Tìm bình phương bán kính nhỏ nhất của đường tròn (tâm tại gốc tọa độ) chứa ít nhất \(k\) điểm.

Đặc tả đầu vào

Dòng đầu tiên chứa \(3\) số nguyên \(a, b, c\) (chỉ nhận giá trị \(0\) hoặc \(1\)), với ý nghĩa số nào bằng \(0\) thì bỏ qua phần xuất kết quả ở câu tương ứng.

Dòng thứ hai chứa số nguyên \(n\), số điểm trên mặt phẳng cho trước.

\(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x, y, c\) \((-10000 \le x, y \le 10000, 1 \le c \le 9)\) lần lượt là hoành độ, tung độ và màu của các điểm.

Dòng cuối cùng chứa số nguyên \(k\) \((1 \le k \le n)\), tham số câu \(c\).

Ghi chú: Các điểm nhập vào đôi một phân biệt.

Đặc tả đầu ra

Câu \(a\): Một dãy số nguyên, cách nhau bởi một dấu cách.

Câu \(b\): Một số nguyên duy nhất.

Câu \(c\): Một số nguyên duy nhất. Nếu không có đường tròn thỏa mãn đề bài, xuất ra \(-1\).

Ghi chú: Máy chấm sẽ tự động bỏ qua những dòng trống và những dấu cách ở cuối dòng.

Tỉ lệ test

\(60\%\) số test có \(a = 1, b = 0, c = 0, n \le 1000\).

\(20\%\) số test có \(a = 1, b = 1, c = 0, n \le 1000\).

\(10\%\) số test có \(a = 1, b = 1, c = 0, n \le 200000\).

\(10\%\) số test có \(a = b = c = 1, n \le 200000\).

Ví dụ

Đầu vào 1:

1 1 1
4
1 2 3
2 2 4
2 4 2
1 4 1
3

Đầu ra 1:

1 2 3 4
6
17

Đầu vào 2:

1 1 0
4
1 2 3
2 2 4
2 4 2
1 4 1
3

Đầu ra 2:

1 2 3 4

6
QDUY

Comments

There are no comments at the moment.