给定两个整数集合（每个集合中没有重复元素），集合元素个数<=100000，求两集合交集，并按非降序输出。
 
 
输入格式:
 
 
第一行是n和m，表示两个集合的元素个数； 接下来是n个数和m个数。
 
 
输出格式:
 
 
第一行输出交集元素个数； 第二行按非降序输出交集元素，元素之间以空格分隔，最后一个元素后面没有空格。
 
 
输入样例:
 
 
在这里给出一组输入。例如：
 
 
5 6
8 6 0 3 1
1 8 9 0 4 5
 
 
输出样例:
 
 
在这里给出相应的输出。例如：
 
 
3
0 1 8
 
 
 
 
 
 
 
 
 
 
 
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{  int n,m;
   int a[100000],b[100000],c[200000];//定义数组 
   cin>>n>>m;//

   for (int i=0; i < n; ++i)
         cin>>a[i];

   for (int i=0; i < m; ++i)
         cin>>b[i];//输入指定的数组数据 

   sort(a,a+n);

   sort(b,b+n);//对数组数据进行排序 

   int i=0,j=0,k=0;

   for (; i<n && j<m;) //判断两个数组的数据大小，用数组c记录下相同的数据，并记录好相等的次数（有多少个交集）
{
       if (a[i]==b[j]) 
            c[k++]=a[i],i++,j++;
      else
      if (a[i]<b[j])
            i++;
      else 
            j++;
}
   cout<<k<<endl;
   for (int i=0; i < k; ++i) 
{
         cout<<c[i];//输出数组，按照要求取好空格与最后没有空格 
   if(i!=k-1)
       {    cout<<" ";}
}
return 0;
}
 
 
 
 
 
此题个人觉得难度在于缩短其时间复杂度，一开始想到的算法运行起来的时间复杂度为O（n^2），由于数据量较大，运行超时，所以考虑的算法是先将数组排好序，再对比取交集。
 
 
将时间复杂度降到O（n*logn）便成功通过。以后考虑运行超时的问题可以优先往这样的方向先考虑。
 
 
 
 
 
转载于:https://www.cnblogs.com/fengwanthousand/p/10545984.html

一、题目
 
 
 
有两个相等长度的正整数序列A和B，都是有序的(递增排序)，同时一个序列中没有重复元素，现在需要求这两个序列的交――序列C，同时打印输出
 
 
二、分析
 首先要注意的是升序，两个集合是有序的。这个在后面是可以作为条件优化的。
 求交集。最直接的方式当然是按照定义，A集合的每一个元素去B集合中寻找，而且是升序，那么查找时一遇到大于的即可判定，为表示交集的元素。而且前一个元素判定的位置可以作为下一个元素开始查找的起点。
 先用数组存储A然后直接逐个输入B中的元素，开始按上述所说判断。判定为交集的用另一个数组储存。最后输出储存交集的数组即可。
 
三、算法实现
 （主要代码）
 
int a[50000];
int b[50000];
int main()
{
    int n,i,x,m,k,j;
    while(scanf("%d",&n)==1&&n!=0)
    {
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        j=0;
        for(k=0; k<n; k++)
        {
            scanf("%d",&x);
            if(k==0)
                i=0;
            else
               i=m;
            for(; i<n; i++)//开始判断
            {
                if(x==a[i])//等于则存入，然后记录当前在A中的位置
                {
                    b[j++]=x;
                    m=i;//m记录位置
                    break;
                }
                else if(x<a[i])//遇到大者，记录位置后，跳出。
                {
                    if(i!=0&&i!=1)
                    m=i-1;//m记录位置
                    break;
                }
            }
        }
        m=j;
        printf("%d",m);
        for(j=0;j<m;j++)
            printf(" %d",b[j]);
        printf("\n");
    }
 
四、算法分析
 时间复杂度：尽管是双层循环，但是第二层其实只是走了一趟，故此算法的时间复杂度为O(n).空间复杂度为O（n).
 优化算法时找到了此题的特点，升序输入。

集合：求A、B两个集合的交集、并集和补集的代码（C语言）
 
 
 
 
 
#include <stdio.h>
#define N 100
main(){
	int a[N],b[N],c[N],d[N];
	int aa[N],bb[N];
	int i,j,k=1;
	int x=1,y=1,z;
	int m,n;
	int flag;
	printf("please input Number of A:\n");
	scanf("%d",&m);
	printf("please input  A:\n");
	for(i=1;i<=m;i++){
		scanf("%d",&a[i]);
	}
	printf("please input Number of B:\n");
	scanf("%d",&n);
	printf("please input  B:\n");
	for(i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	for(i=1;i<=m;i++){
		    flag=0;
			for(j=1;j<=n;j++){
				if(a[i]==b[j]){c[k]=a[i];k++;flag=1;continue;}
			}
			if(flag==0){
				aa[x]=a[i];x++;}
	}
	for(i=1;i<=n;i++){
		    flag=0;
			for(j=1;j<=m;j++){
				if(a[j]==b[i]){flag=1;continue;}
			}
			if(flag==0){
				bb[y]=b[i];y++;}
	}
	printf("A-A与B的交集:共%d个\n",x-1);
	for(i=1;i<x;i++){printf("%d ",aa[i]);}printf("\n");
	printf("B-A与B的交集:共%d个\n",y-1);
	for(i=1;i<y;i++){printf("%d ",bb[i]);}printf("\n");
	printf("A与B的交集:共%d个\n",k-1);
	for(i=1;i<k;i++){printf("%d ",c[i]);}printf("\n");
	printf("A与B的并集:共%d个\n",x+y+k-3);
	for(i=1;i<x;i++){printf("%d ",aa[i]);}
	for(i=1;i<y;i++){printf("%d ",bb[i]);}
	for(i=1;i<k;i++){printf("%d ",c[i]);}printf("\n");

}
 

 测试例：
 
4
 1 2 3 4
 8
 1 3 4 5 6 7 8 9
 
运行结果：
 
 
 
 

基础概念
 
简单多边形 P 的核(kernel)，K（p）定义如下：K（p）由多边形内部的点构成，这些点与多边形的任何顶点相连所构成的线段完全包含在 P 中。
 一个重要的性质是现，K（p）作为半平面的交集，它或者为空或者为完全包含在P 内的有界凸集。
 
 红色部分。
 
半平面，在数学定义下就是
 ax + by + c >= 0
 所控制的一个的半空间。半空间在不同维度下意义不同，如果是2维的话，其实此时ax + by + c >= 0 就是二维中一条直线的一侧。
 
此时如果你再看核，其实可以理解为线性规划时得到的一个可行域。
 
我们上面说到 如果是2维的话，其实此时ax + by + c >= 0 就是二维中一条直线的一侧。所以直线（也就是决定半平面的直线）切割多边形 ，让直线不断的去切割当前多边形，然后得到新的多边形。
 
不难想象，其实结果可能是一个多边形（一定是凸的）、一个线段、空、一个点等等。我们记录顶点的数据来进行描述。
 
综上，如果计算半平面的交集，可以使用一个
 
将直线们极角排序,角度相同的保留下需要的一个
用一个双端队列存储当前半平面交,每次通过判断队首与队尾第一个交点是否满足当前直线来更新
先用队尾判定队首交点是否合法,再用队首判断队尾交点是否合法
最后求出来的半平面交是一个凸多边形
 
同理如果计算多边形交，可以将每一个边对应到一个半平面，从而运行半平面交集进行计算。
 
Ref
 
https://blog.csdn.net/weixin_30345577/article/details/97505934
 https://blog.csdn.net/accry/article/details/6070621