http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1347. 极点统计
时间限制:10.0s   内存限制:256.0MB  
总提交次数:34   AC次数:1   平均分:35.59
将本题分享到:
   
 
问题描述
  对于一个由平面上点组成的集合S,以及一个平面上的点p,函数f(p,S)当且仅当p在S的凸包内部(包括S的凸包的边界)时值为1,其余情况下其值为0。
  现给定两个平面上的点集P={p_1,p_2,…,p_N }和A={a_1,a_2,…,a_M },我们称A中的一个点a_i为极点,当且仅当其满足

  也就是说,a_i不在任意 A 集合中非 a_i 的点与P组成的凸包内部。
  请统计出集合A中极点的个数。
输入格式
  输入第一行包含两个用空格隔开的正整数N和M;
  第二行包含N个用空格隔开的整数对,第i个数对(x_i^p,y_i^p)表示点p_i的坐标;
  第二行包含M个用空格隔开的整数对,第j个数对(x_j^a,y_j^a)表示点a_j的坐标。
  对于同一个集合,输入数据保证不会出现坐标相同的两个点。
输出格式
  输出包含一行一个整数,表示集合A中极点的个数。
样例输入
4 5
6 3 7 -1 -6 -5 1 5
-5 -5 7 -5 9 -9 -10 11 -5 -6
样例输出
3
样例说明
  极点分别为(-10,11),(9,-9)以及(-5,-6)。
数据规模和约定
  对于10%的数据满足M=1;
  对于30%的数据满足N,M≤50;
  对于另外30%的数据满足N≤10,M≤20000;
  对于100%的数据满足3≤N≤ 〖10〗^5,1≤M≤〖10〗^5,|x_i |,|y_i |≤〖10〗^6,且点集P的凸包面积不为0。