包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

				#include 
				#include 
				#include 
				#include 
				#include 
				#include 
				using namespace std;
				
				//ZOJ 1610 线段树的颜色覆盖 
				#define NMAX 8200
				
				typedef struct dian
				{
					int left;
					int right;
					int color;//初始color为-1,若颜色混合，为-10
				}dian;
				
				dian tree[NMAX*4];
				int ccount[NMAX];
				int has[NMAX];
				int qujian[NMAX];
				int sss;
				
				void create_tree(int p,int l,int r)
				{
					tree[p].left=l;tree[p].right=r;tree[p].color=-1;
					if(l+1==r) return;
					create_tree(2*p,l,(l+r)/2);
					create_tree(2*p+1,(l+r)/2,r);
				}
				
				void insert_tree(int p,int l,int r,int c)
				{
					int mid=(tree[p].left+tree[p].right)/2;
					if(tree[p].left==l&&tree[p].right==r) tree[p].color=c;
					else
					{
						if(tree[p].color>=-1&&tree[p].right-tree[p].left>1) 
						{
							tree[2*p].color=tree[p].color;
							tree[2*p+1].color=tree[p].color;
							tree[p].color=-10;
						}
						if(r						else if(l>=mid) insert_tree(2*p+1,l,r,c);
						else
						{
							insert_tree(2*p,l,mid,c);
							insert_tree(2*p+1,mid,r,c);
						}
					}
				}
				/*
				void count_solve2(int p)
				{	//一次编列树，把找到的颜色（不管同一颜色想不想接）按次序放到一个数组里
					if(tree[p].color>=-1) 
					{
						qujian[++sss]=tree[p].color;
				//		qujian[++sss]=tree[p].right;
					}
					else if(tree[p].color==-10)
					{
						count(2*p);
						count(2*p+1);
					}
				}
				*/
				void print()
				{
					int i;
					for(i=1;i					cout				}
				/*
				void solve2()
				{	//方法2
					//一次编列树，把找到的颜色（不管同一颜色想不想接）按次序放到一个数组里
					//统计时编列数组，跳过数组中相邻的相同颜色计数
					int i;
					count(1);
				//	print();
					i=1;
					while(qujian[i]==-1) i++;
					ccount[qujian[i]]=1;
					i++;
					for(;i					{	//跳过相邻的相同颜色
						if(qujian[i-1]!=qujian[i]&&qujian[i]!=-1) ccount[qujian[i]]++;
					}
					for(i=0;i					{
						if(ccount[i]>0) printf("%d %d\n",i,ccount[i]);
					}
					printf("\n");
				}
				*/
				void count_solve1(int p,int &lc,int &rc)
				{//统计颜色的段数
					int lmc,rmc;
					if(tree[p].color>=-1) 
					{	//被一种颜色覆盖
						if(tree[p].color>=0) ccount[tree[p].color]++;//找到一个颜色
						lc=tree[p].color;//上一层函数需要
						rc=tree[p].color;
					}
					else if(tree[p].color==-10)
					{	//多颜色覆盖
						if(tree[p].right-tree[p].left>1)
						{	//递归地求子节点颜色
							count_solve1(2*p,lc,lmc);
							count_solve1(2*p+1,rmc,rc);
							if(lmc==rmc&&lmc!=-1) ccount[lmc]--;//如果两颗子树相邻的两颜色相等			
						}
					}
				}
				
				void solve1()
				{	//方法1
					//一次编列树，边编列边修正ccount[]
					int i,a,b;
					count_solve1(1,a,b);
					for(i=0;i					{
						if(has[i]==1&&ccount[i]>0)
						{
							printf("%d %d\n",i,ccount[i]);
						}
					}
					printf("\n");
				}
				
				int main()
				{
					int i,num,la,ra,ca,tt;
					double fe,fs;
					while(scanf("%d",&num)!=EOF)
					{
						fs=clock();
						sss=0;
						memset(has,0,sizeof(has));
						memset(ccount,0,sizeof(ccount));
						create_tree(1,0,NMAX);
						for(i=1;i						{
							scanf("%d%d%d",&la,&ra,&ca);
							if(ra							{
								tt=la;
								la=ra;
								ra=tt;
							}
							if(la!=ra) insert_tree(1,la,ra,ca);
							has[ca]=1;
						}
						fe=clock();
						solve1();
						if(((double)(fe-fs))/CLOCKS_PER_SEC*1000>300) printf("no");
					}
					return 0;
				}