包括计算几何、特殊数据结构、组合数学等知识点的代码

//POJ 1177 /* //#include <iostream> #include <stdio.h> //include <algorithm> #include <math.h> #include <stdlib.h> #include <time.h> //using namespace std; #define NMAX 30000 #define MAX 99999999 typedef struct noid { int low; int high; int len;//测度 int line;//连续段数 int cc;//覆盖的线段个数 int lcover,rcover;//左右端点是否被覆盖 }noid; typedef struct shuxian { int tag;//矩形的左竖线还是右竖线 int x;//横坐标 int y1;//低位纵坐标 int y2;//高位纵坐标 }shuxian; noid tree[NMAX*3]; shuxian shuru[NMAX]; shuxian chuli[NMAX]; int lisan[NMAX*2]; int temp[NMAX*2]; int lsnum;//离散后的不重复的纵坐标个数 void print_tree_lh() { int i; printf("this is tree's low and high\n"); for(i=1;i<=lsnum*3;i++) { printf("[%d %d]",tree[i].low,tree[i].high); if(i==1||i==3||i==7||i==15||i==31) printf("\n"); } system("pause"); } void print_tree_llc() { int i; printf("this is tree's len, line and cc\n"); for(i=1;i<=lsnum*3;i++) { printf("[%d %d %d %d %d]",tree[i].len,tree[i].line,tree[i].cc,tree[i].lcover,tree[i].rcover); if(i==1||i==3||i==7||i==15||i==31) printf("\n"); } system("pause"); } int cmpint(const void *a,const void *b) { return (*(int *)a)-(*(int *)b); } int search_y(int key) { int *p; p=(int *)bsearch(&key,lisan+1,lsnum,sizeof(int),cmpint); return p-lisan; } int cmppos(const void * a,const void * b) { int tt=(((struct shuxian *)a)->x)-(((struct shuxian *)b)->x); if(tt==0) return (((struct shuxian *)a)->tag)-(((struct shuxian *)b)->tag); return tt; } void create(int p,int l,int h) { int mid; mid=(l+h)/2; tree[p].low=l; tree[p].high=h; tree[p].len=tree[p].line=tree[p].cc=0; if(h-l>1) { create(p*2,l,mid); create(p*2+1,mid,h); } } void update(int p) { if(p>=8000) printf("no\n"); // printf("update (1) p=%d low=%d high=%d\n",p,tree[p].low,tree[p].high); if(tree[p].cc > 0) { tree[p].lcover=tree[p].rcover=tree[p].line=1; tree[p].len=lisan[tree[p].high]-lisan[tree[p].low]; // printf("update (2) tree[%d].len=%d\n",p,tree[p].len); // print_tree_llc(); } else { if(tree[p].low+1 != tree[p].high) { tree[p].lcover=tree[2*p].lcover; tree[p].rcover=tree[2*p+1].rcover; tree[p].len=tree[2*p].len + tree[2*p+1].len; tree[p].line=tree[2*p].line + tree[2*p+1].line - tree[2*p].rcover * tree[2*p+1].lcover; // print_tree_llc(); } else { tree[p].len=tree[p].lcover=tree[p].rcover=tree[p].line=0; // print_tree_llc(); } } } void insert(int p,int l,int h) { int mid; if(p>=8000) printf("no\n"); // printf("insert p=%d l=%d h=%d\n",p,l,h); mid=(tree[p].low+tree[p].high)/2; if(l<=tree[p].low && h>=tree[p].high) tree[p].cc++; else { if(l<mid) insert(2*p,l,h); if(h>mid) insert(2*p+1,l,h); } update(p); } void ddelete(int p,int l,int h) { int mid; if(p>=8000) printf("no\n"); mid=(tree[p].low+tree[p].high)/2; if(l<=tree[p].low && h>=tree[p].high) tree[p].cc--; else { if(l<mid) ddelete(2*p,l,h); if(h>mid) ddelete(2*p+1,l,h); } update(p); } void init(int num) { int i,j; for(i=1;i<=num;i++) { // printf("init (1) shuru[%d]=%d\n",i,shuru[i].x); } for(i=1;i<=num;i++) chuli[i]=shuru[i]; for(i=1;i<=num;i++) qsort(chuli+1,num,sizeof(shuxian),cmppos); for(i=1;i<=num;i++) { // printf("init (2) chuli[%d]=%d\n",i,chuli[i].x); } for(i=1,j=0;i<=num;i++) { temp[++j]=chuli[i].y1; temp[++j]=chuli[i].y2; } qsort(temp+1,num*2,sizeof(int),cmpint); lisan[1]=temp[1]; for(i=2,j=1;i<=2*num;i++) { if(temp[i]!=temp[i-1]) lisan[++j]=temp[i]; } lsnum=j; for(i=1;i<=lsnum;i++) { // printf("init (3) lisan[%d]=%d\n",i,lisan[i]); } for(i=1;i<=lsnum;i++) { // printf("init (4) %d == %d\n",lisan[i],search_y(lisan[i])); } create(1,1,j); // print_tree_lh(); // system("pause"); } int solve(int num) { int i,lastx,lasty,ans=0,be,end,qq; be=search_y(chuli[1].y1); end=search_y(chuli[1].y2); // printf("solve (1)\n"); insert(1,be,end); lastx=chuli[1].x; lasty=tree[1].len; ans+=tree[1].len; // printf("ans=%d\n",ans); // print_tree_llc(); for(i=2;i<=num;i++) { be=search_y(chuli[i].y1); end=search_y(chuli[i].y2); qq=2*tree[1].line*(chuli[i].x-chuli[i-1].x); ans+=qq; if(chuli[i].tag==1) insert(1,be,end); else ddelete(1,be,end); // printf("this is %d's line\n",i); // print_tree_llc(); ans+=abs(tree[1].len-lasty); // printf("solve (2) henxian=%d shuxian=%d ans=%d\n",qq,abs(tree[1].len-lasty),ans); // system("pause"); lastx=chuli[i].x; lasty=tree[1].len; } return ans; } int main() { int num,i,ax,ay,bx,by; scanf("%d",&num); for(i=1;i<=num;i++) { scanf("%d%d%d%d",&ax,&ay,&bx,&by); shuru[2*i-1].tag=1;//左边 shuru[2*i-1].x=ax; shuru[2*i-1].y1=ay; shuru[2*i-1].y2=by; shuru[2*i].tag=-1; shuru[2*i].x=bx; shuru[2*i].y1=ay; shuru[2*i].y2=by; } init(2*num); printf("%d\n",solve(2*num)); scanf("%d %d",&num,&num); return 0; } */ #include <stdio.h> #include <math.h> #include <stdlib.h> #define MAX 10000 struct node { int be,end,pos,tag; }rect[MAX+1]; int line[2*MAX],len[2*MAX]; int b[2*MAX],e[2*MAX]; int cnt[2*MAX]; int lchild[2*MAX],rchild[2*MAX]; int lcover[2*MAX],rcover[2*MAX]; int tmp[MAX+1],aux[MAX+1]; int all,num,n; int cmpint(const void *m,const void *n) { return *((int *)m) - *((int *)n); } int cmprect(const void *m,const void *n) { return ((struct node*)m)->pos - ((struct node *)n)->pos; } int search(int key) { int *p; p=(int *)bsearch(&key,tmp+1,num,sizeof(int),cmpint); return p-tmp; } void build(int be,int end) { int x=++all; b[x]=be; e[x]=end; cnt[x]=0; len[x]=0; line[x]=0; lcover[x]=rcover[x]=0; if(end-be>1) { lchild[x]=all+1; build(be,(be+end)/2); rchild[x]=all+1; build((be+end)/2,end); } } void update(int root,int be,int end) { if(cnt[root]>0) { len[root]=tmp[end]-tmp[be]; lcover[root]=rcover[root]=1; line[root]=1; } else if(end-be>1) { len[root]=len[lchild[root]] + len[rchild[root]]; lcover[root] = lcover[lchild[root]]; rcover[root] = rcover[rchild[root]]; line[root] = line[lchild[root]] + line[rchild[root]] - rcover[lchild[root]] * lcover[rchild[root]]; } else { len[root]=line[root]=lcover[root]=rcover[root]=0; } } void insert(int root,int be,int end) { if(be<=b[root] && end>=e[root]) cnt[root]++; else { if(be<(b[root]+e[root])/2) insert(lchild[root],be,end); if(end>(b[root]+e[root])/2) insert(rchild[root],be,end); } update(root,b[root],e[root]); } void del(int root,int be,int end) { if(be<=b[root] && end>=e[root]) cnt[root]--; else { if(be<(b[root]+e[root])/2) del(lchild[root],be,end); if(end>(b[root]+e[root])/2) del(rchild[root],be,end); } update(root,b[root],e[root]); } void input() { int i; int x1,y1,x2,y2; scanf("%d",&n); for(i=1;i<=2*n;i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); rect[i].be=y1; rect[i].end=y2; rect[i].tag=1; rect[i].pos=x1; aux[i]=y1; i++; rect[i].be=y1; rect[i].end=y2; rect[i].tag=0; rect[i].pos=x2; aux[i]=y2; } } void discrete() { int i; qsort(rect+1,2*n,sizeof(struct node),cmprect); qsort(aux+1,2*n,sizeof(int),cmpint); num=1; tmp[1]=aux[1]; for(i=2;i<=2*n;i++) { while(i<=2*n && aux[i]==aux[i-1]) i++; tmp[++num]=aux[i]; } } int solve() { int sum,last,i,left,right; all=0; build(1,num); sum=0; last=0; for(i=1; i<=2*n-1; i++) { left= search(rect[i].be); right= search(rect[i].end); if(rect[i].tag) insert(1,left,right); else del(1,left,right); sum+=2*(rect[i+1].pos-rect[i].pos)*line[1]; sum+=abs(len[1]-last); last=len[1]; } left=search(rect[i].be); right=search(rect[i].end); del(1,left,right); sum+=abs(len[1]-last); return sum; } int main() {