#PQJ85x10790. QOJ 85_10790

    ID: 3047 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTSC 2012计算几何枚举

QOJ 85_10790

IOI2012 中国队选拔赛暨精英赛 第二试 极点统计 极点统计 【问题描述】 对于一个由平面上点组成的集合𝑆,以及一个平面上的点𝑝,函数𝑓(𝑝, 𝑆)当且 仅当𝑝在S 的凸包内部(包括S 的凸包的边界)时值为1,其余情况下其值为0。 现给定两个平面上的点集𝑃= {𝑝1, 𝑝2, … , 𝑝𝑁}和𝐴= {𝑎1, 𝑎2, … , 𝑎𝑀},我们称𝐴 中的一个点𝑎𝑖为极点,当且仅当其满足 ∑𝑓(𝑎𝑖, 𝑃∪{𝑎𝑗}) = 0 𝑗≠𝑖 也就是说,𝑎𝑖不在任意 𝐴 集合中非 𝑎𝑖 的点与P 组成的凸包内部。 请统计出集合𝐴中极点的个数。 【输入格式】 输入文件extreme.in 的第一行包含两个用空格隔开的正整数𝑁和𝑀; 𝑝, 𝑦𝑖 𝑝)表示点𝑝𝑖的坐标; 第二行包含𝑁个用空格隔开的整数对,第𝑖个数对(𝑥𝑖 𝑎, 𝑦𝑗 𝑎)表示点𝑎𝑗的坐标。 第二行包含𝑀个用空格隔开的整数对,第𝑗个数对(𝑥𝑗 对于同一个集合,输入数据保证不会出现坐标相同的两个点。 【输出格式】 输出文件extreme.out 仅包含一行一个整数,表示集合𝐴中极点的个数。 【样例输入】 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%的数据满足𝑀= 1; 对于30%的数据满足𝑁, 𝑀≤50; 对于另外30%的数据满足𝑁≤10,𝑀≤20000; 对于100%的数据满足3 ≤N ≤ 105, 1 ≤M ≤105,|𝑥𝑖|, |𝑦𝑖| ≤106,且点集𝑃 的凸包面积不为0。 第4 页 共5 页