再度上映打表“圣人”

1760 极点统计

2012年CTSC国家队选拔赛

 时间限制: 3 s

 空间限制: 256000 KB

 题目等级 : 大师 Master

题解

题目描述 Description

　　对于一个由平面上点组成的集合S，以及一个平面上的点p，函数f(p,S)当且仅当p在S的凸包内部（包括S的凸包的边界）时值为1，其余情况下其值为0。
　　现给定两个平面上的点集P={p1,p2,…,pN }和A={a1,a2,…,aM }，我们称A中的一个点ai为极点，当且仅当其满足

　　也就是说，ai不在任意 A 集合中非 ai 的点与P组成的凸包内部。
　　请统计出集合A中极点的个数。

输入描述 Input Description

　　输入第一行包含两个用空格隔开的正整数N和M；
　　第二行包含N个用空格隔开的整数对，第i个数对(xip,yip)表示点pi的坐标；
　　第三行包含M个用空格隔开的整数对，第j个数对(xja,yja)表示点aj的坐标。
　　对于同一个集合，输入数据保证不会出现坐标相同的两个点。

输出描述 Output Description

　　输出包含一行一个整数，表示集合A中极点的个数。

样例输入 Sample Input

4 5
6 3 7 -1 -6 -5 1 5
-5 -5 7 -5 9 -9 -10 11 -5 -6

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

【样例解释】

　　极点分别为(-10,11)，(9,-9)以及(-5,-6)。

【数据规模】

　　对于10%的数据满足M = 1；
　　对于30%的数据满足N,M ≤ 50；
　　对于另外30%的数据满足N ≤ 10，M ≤ 20000；
　　对于100%的数据满足3 ≤ N ≤ 105, 1 ≤ M ≤ 105，|xi |,|yi | ≤ 106，且点集P的凸包面积不为0。

佩服佩服

#include<cstdio>
int main()
{
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=2*n;i++)scanf("%*d");
    for(i=1;i<=2*m;i++)scanf("%*d");
    if(n==3&&m==1){printf("1");return 0;}
    if(n==98901&&m==99720){printf("75080");return 0;}
    if(n==18&&m==50){printf("26");return 0;}
    if(n==40&&m==50){printf("17");return 0;}
    if(n==10&&m==19597){printf("8195");return 0;}
    if(n==10&&m==19855){printf("8976");return 0;}
    if(n==10&&m==19565){printf("8516");return 0;}
    if(n==17067&&m==38168){printf("27371");return 0;}
    if(n==68952&&m==89603){printf("67197");return 0;}
    if(n==78933&&m==99666){printf("74963");return 0;}
}
牛逼，牛逼！！