T39280

T39280 k-NN

---

题目描述

k -NN 是机器学习中常用的算法，其简化版的流程如下：

给出n$n$个点(xi,yi)$(x_i,y_i)$，每个点有一个颜色，为红色或黑色。现在给出一个询问位置(x,y)$(x,y)$，这个位置的颜色将由离它最近的k$k$个点决定：如果离它最近的k$k$个点中，红色点的个数大于等于黑色点的个数，那么这个位置为红色，否则为黑色。

Bob现在得到了这n$n$个点，以及询问的位置，他想知道：有多少个k$k$(1≤k≤n)$(1\le k\le n)$，可以使这个询问位置的颜色为红色。

两个点(x1,y1)$(x_1,y_1)$,(x2,y2)$(x_2,y_2)$的距离定义为(x1−x2)2+(y1−y2)2−−−−−−−−−−−−−−−−−−√$\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$。如果询问点到某两个点的距离相同，那么编号较小的视作距离较近。

---

输入输出格式

输入格式：

第一行三个整数n,x,y$n,x,y$，意义如上所述。
接下来n$n$行，每行三个整数(xi,yi,ci)$(x_i,y_i,c_i)$，xi,yi$x_i,y_i$的意义如上所述，ci$c_i$表示颜色，ci=1$c_i=1$表示这个点为红色，ci=2$c_i=2$表示这个点为黑色。

输出格式：

一行一个整数，表示答案。

输入输出样例

输入样例#1：

3 1 1
1 1 1
2 2 2
3 3 2

输出样例#1：

2

输入样例#2：

3 1 1
1 1 2
2 2 1
3 3 1

输出样例#2：

2

说明

对于30%$30\mathrm{\%}$的数据，满足1≤n≤1000$1\le n\le 1000$。
对于100%$100\mathrm{\%}$的数据，满足1≤n≤105$1\le n\le {10}^5$，1≤xi,yi,x,y≤109$1\le x_i,y_i,x,y\le {10}^9$。