Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

郁闷，一直WA，用线段树写的，我知道哪组数据过不了，但不知道原因，求人分析代码，有详细的注释～～～跪求～～

Posted by ccyjava at 2010-10-13 15:08:12 on Problem 1177 and last updated at 2010-10-13 15:10:02

#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#include "string.h"
typedef struct segtree{//线段树的结构
	int count;
	int m;
	int line;
	int lb,rb;
	int l,r;
	struct segtree *lc,*rc;
}*st,stnode;
typedef struct rec{//矩形的结构
	int x1,x2;
	int y1,y2;
}rect;
typedef struct lin{//每条竖线的结构
	int y1,y2;
	int in;
	int x;
}vet;
//====================================线段树的操作==================================
void updatem(st &);
void updateline(st&);
st creatit(int i,int j){//建树
	int k;
	st now=(st)malloc(sizeof(stnode));
	now->l=i;
	now->r=j;
	now->count=0;
	now->m=0;
	now->line=0;
	now->lb=0;
	now->rb=0;
	now->lc=NULL;
	now->rc=NULL;
	if(j-i>1){
		k=(i+j)/2;
		if(i<k){
			now->lc=creatit(i,k);
		}
		if(j>k){
			now->rc=creatit(k,j);
		}
	}
	return now;
}
int dropit(st &s){//销毁树
	if(s->lc!=NULL)
		dropit(s->lc);
	if(s->rc!=NULL)
		dropit(s->rc);
	free(s);
	return 0;
}
int insertit(st &s,int i,int j){//插入线段
	int k;
	if(s==NULL)
		return 0;
	if(i<=s->l&&j>=s->r){
		s->count++;
	}else{
		k=(s->l+s->r)/2;
		if(i<k){
			insertit(s->lc,i,j);
		}
		if(j>k){
			insertit(s->rc,i,j);
		}
	}
	updatem(s);
	updateline(s);
	return 1;
}

int deleteit(st &s,int i,int j){//删除线段
	int k;
	if(s==NULL)
		return 0;
	if(i<=s->l&&j>=s->r){
		s->count--;
	}else{
		k=(s->l+s->r)/2;
		if(i<k){
			deleteit(s->lc,i,j);
		}
		if(j>k){
			deleteit(s->rc,i,j);
		}
	}
	updatem(s);
	updateline(s);
	return 1;
}
void updatem(st &s){//更新度
	if(s->count>0){
		s->m=s->r-s->l;
	}
	else{
		if(s->r-s->l==1){
			s->m=0;
		}else{
			s->m=s->lc->m+s->rc->m;
		}
	}
}
void updateline(st &s){//更新line
	if(s->count>0){
		s->line=1;
		s->lb=1;
		s->rb=1;
	}else{
		if(s->r-s->l==1){
			s->line=0;
			s->lb=0;
			s->rb=0;
		}
		else{
			s->lb=s->lc->lb;
			s->rb=s->rc->rb;
			s->line=s->lc->line+s->rc->line-s->lc->rb*s->rc->lb;
		}
	}
}
int getinm(st s,int i,int j){//求i到j的度
	int r=0;
	int k;
	k=(s->l+s->r)/2;
	if(i<=s->l&&j>=s->r){
		r+=s->m;
		return r;
	}
	if(i>=s->r||j<=s->l){
		return r;
	}
	if(i<k)
		r+=getinm(s->lc,i,j);
	if(j>k)
		r+=getinm(s->rc,i,j);
	return r;
}
int getinline(st s,int i,int j){//求i到j的line
	int r=0;
	int k;
	k=(s->l+s->r)/2;
	if(i<=s->l&&j>=s->r){
		r+=s->line;
		return r;
	}
	if(i>=s->r||j<=s->l){
		return r;
	}
	if(i<k)
		r+=getinline(s->lc,i,j);
	if(j>k)
		r+=getinline(s->rc,i,j);
	return r;
}
//=============================================================================
int n;//矩形的个数
int nn;//涉及到的横坐标的个数
rect r;//一个矩形
int tmap[10000];//临时存储的横坐标
int xmap[10000];//去除了重复后的横坐标
vet v[10000];//所有矩形竖线
int cmp(const void *a,const void *b){
	return *(int*)a-*(int*)b;
}
int cmpv(const void *a,const void *b){
	vet & x=*(vet*)a;
	vet & y=*(vet*)b;
	return x.x-y.x;
}
int abss(int a){//求绝对值
	if(a<0)
		return -a;
	else
		return a;
}
int main(){
	int i,j;
	int lastm,lastline,nowm,nowline;
	st l;
	int re=0;
	int miny=99999,maxy=-99999;
	while(scanf("%d",&n)!=EOF){
		if(n>0){
			for(i=0;i<n;i++){
				scanf("%d%d%d%d",&r.x1,&r.y1,&r.x2,&r.y2);
				//分出横坐标
				tmap[i*2]=r.x1;
				tmap[i*2+1]=r.x2;
				//分出竖线
				v[i*2].in=1;
				v[i*2].x=r.x1;
				v[i*2].y1=r.y1;
				v[i*2].y2=r.y2;
				v[i*2+1].in=0;
				v[i*2+1].x=r.x2;
				v[i*2+1].y1=r.y1;
				v[i*2+1].y2=r.y2;
				//找出y的范围
				if(r.y1<miny)
					miny=r.y1;
				if(r.y2>maxy)
					maxy=r.y2;
			}
			
			qsort(tmap,n*2,sizeof(int),cmp);
			qsort(v,n*2,sizeof(vet),cmpv);
			//======================debug=================================
			for(i=0;i<2*n;i++){
				
				printf("%d\n",i);
				printf("%d %d %d %d\n",v[i].x,v[i].y1,v[i].y2,v[i].in);
				
			}
			//============================================================
			xmap[0]=tmap[0];
			for(i=1,j=0;i<2*n;i++){//得到去除了重复值的横坐标
				if(tmap[i]!=xmap[j]){
					j++;
					xmap[j]=tmap[i];
				}
			}
			nn=j+1;
			l=creatit(miny,maxy);
			lastm=0;
			lastline=0;
			for(i=0,j=0;i<nn;i++){//遍历每个横坐标
				for(;j<2*n;j++){//遍历该横坐标上的竖线
					if(v[j].x!=xmap[i])
						break;
					if(v[j].in==1)//插入线段
						insertit(l,v[j].y1,v[j].y2);
					if(v[j].in==0)//删除线段
						deleteit(l,v[j].y1,v[j].y2);
				}
				nowline=l->line;
				nowm=l->m;
				if(i!=nn-1)
				re+=((xmap[i+1]-xmap[i])*2*nowline);//不是最后一个，就把横向线段长度添加到结果里
				re+=abss(nowm-lastm);//添加竖向的线段长度
				lastm=nowm;
				lastline=nowline;
			}
		}
		printf("%d\n",re);
	}
	dropit(l);
	return 0;
}

//=======================我过不了的数据===================================

47
-1105 -1155 -930 -285
-765 -1115 -615 -375
-705 -480 -165 -285
-705 -1200 -175 -1025
-275 -1105 -105 -385
-10 -1165 185 -285
315 -1160 400 -710
340 -1195 655 -1070
580 -1140 655 -265
325 -480 395 -335
365 -390 620 -265
365 -770 610 -665
815 -1195 1110 -1070
825 -760 1100 -660
810 -405 1115 -275
780 -700 860 -360
1065 -695 1130 -360
775 -1110 860 -735
1070 -1110 1145 -730
-1065 -95 140 260
-725 80 750 460
135 -135 490 840
135 -135 490 750
-520 40 -210 945
-595 620 215 695
670 -5 855 610
550 -75 830 -25
815 240 1085 370
980 -90 1125 145
280 150 490 315
-1035 -155 -845 -90
855 815 950 1030
785 980 860 1165
945 985 1015 1160
730 835 1075 895
875 695 935 790
-1165 420 -520 650
-1090 815 -210 945
-130 800 65 1160
120 980 690 1150
-1140 995 -125 1180
-825 1050 -195 1135
-90 865 10 1090
280 1045 625 1090
-655 1065 -245 1115
-1155 70 -790 315
-1005 110 -825 225


我输出：36790
该输出：37000

Followed by:

过了3个月，我自己解决了～～～～～～～ (2625) ccyjava 2010-12-01 18:00:31
- Re:攒~~~ (2915) CalmDown 2010-12-01 18:24:25

Post your reply here:

User ID:
Password:
Title:

Content:

> #include "stdio.h"
> #include "malloc.h"
> #include "stdlib.h"
> #include "string.h"
> typedef struct segtree{//线段树的结构
> 	int count;
> 	int m;
> 	int line;
> 	int lb,rb;
> 	int l,r;
> 	struct segtree *lc,*rc;
> }*st,stnode;
> typedef struct rec{//矩形的结构
> 	int x1,x2;
> 	int y1,y2;
> }rect;
> typedef struct lin{//每条竖线的结构
> 	int y1,y2;
> 	int in;
> 	int x;
> }vet;
> //====================================线段树的操作==================================
> void updatem(st &);
> void updateline(st&);
> st creatit(int i,int j){//建树
> 	int k;
> 	st now=(st)malloc(sizeof(stnode));
> 	now->l=i;
> 	now->r=j;
> 	now->count=0;
> 	now->m=0;
> 	now->line=0;
> 	now->lb=0;
> 	now->rb=0;
> 	now->lc=NULL;
> 	now->rc=NULL;
> 	if(j-i>1){
> 		k=(i+j)/2;
> 		if(i<k){
> 			now->lc=creatit(i,k);
> 		}
> 		if(j>k){
> 			now->rc=creatit(k,j);
> 		}
> 	}
> 	return now;
> }
> int dropit(st &s){//销毁树
> 	if(s->lc!=NULL)
> 		dropit(s->lc);
> 	if(s->rc!=NULL)
> 		dropit(s->rc);
> 	free(s);
> 	return 0;
> }
> int insertit(st &s,int i,int j){//插入线段
> 	int k;
> 	if(s==NULL)
> 		return 0;
> 	if(i<=s->l&&j>=s->r){
> 		s->count++;
> 	}else{
> 		k=(s->l+s->r)/2;
> 		if(i<k){
> 			insertit(s->lc,i,j);
> 		}
> 		if(j>k){
> 			insertit(s->rc,i,j);
> 		}
> 	}
> 	updatem(s);
> 	updateline(s);
> 	return 1;
> }
> 
> int deleteit(st &s,int i,int j){//删除线段
> 	int k;
> 	if(s==NULL)
> 		return 0;
> 	if(i<=s->l&&j>=s->r){
> 		s->count--;
> 	}else{
> 		k=(s->l+s->r)/2;
> 		if(i<k){
> 			deleteit(s->lc,i,j);
> 		}
> 		if(j>k){
> 			deleteit(s->rc,i,j);
> 		}
> 	}
> 	updatem(s);
> 	updateline(s);
> 	return 1;
> }
> void updatem(st &s){//更新度
> 	if(s->count>0){
> 		s->m=s->r-s->l;
> 	}
> 	else{
> 		if(s->r-s->l==1){
> 			s->m=0;
> 		}else{
> 			s->m=s->lc->m+s->rc->m;
> 		}
> 	}
> }
> void updateline(st &s){//更新line
> 	if(s->count>0){
> 		s->line=1;
> 		s->lb=1;
> 		s->rb=1;
> 	}else{
> 		if(s->r-s->l==1){
> 			s->line=0;
> 			s->lb=0;
> 			s->rb=0;
> 		}
> 		else{
> 			s->lb=s->lc->lb;
> 			s->rb=s->rc->rb;
> 			s->line=s->lc->line+s->rc->line-s->lc->rb*s->rc->lb;
> 		}
> 	}
> }
> int getinm(st s,int i,int j){//求i到j的度
> 	int r=0;
> 	int k;
> 	k=(s->l+s->r)/2;
> 	if(i<=s->l&&j>=s->r){
> 		r+=s->m;
> 		return r;
> 	}
> 	if(i>=s->r||j<=s->l){
> 		return r;
> 	}
> 	if(i<k)
> 		r+=getinm(s->lc,i,j);
> 	if(j>k)
> 		r+=getinm(s->rc,i,j);
> 	return r;
> }
> int getinline(st s,int i,int j){//求i到j的line
> 	int r=0;
> 	int k;
> 	k=(s->l+s->r)/2;
> 	if(i<=s->l&&j>=s->r){
> 		r+=s->line;
> 		return r;
> 	}
> 	if(i>=s->r||j<=s->l){
> 		return r;
> 	}
> 	if(i<k)
> 		r+=getinline(s->lc,i,j);
> 	if(j>k)
> 		r+=getinline(s->rc,i,j);
> 	return r;
> }
> //=============================================================================
> int n;//矩形的个数
> int nn;//涉及到的横坐标的个数
> rect r;//一个矩形
> int tmap[10000];//临时存储的横坐标
> int xmap[10000];//去除了重复后的横坐标
> vet v[10000];//所有矩形竖线
> int cmp(const void *a,const void *b){
> 	return *(int*)a-*(int*)b;
> }
> int cmpv(const void *a,const void *b){
> 	vet & x=*(vet*)a;
> 	vet & y=*(vet*)b;
> 	return x.x-y.x;
> }
> int abss(int a){//求绝对值
> 	if(a<0)
> 		return -a;
> 	else
> 		return a;
> }
> int main(){
> 	int i,j;
> 	int lastm,lastline,nowm,nowline;
> 	st l;
> 	int re=0;
> 	int miny=99999,maxy=-99999;
> 	while(scanf("%d",&n)!=EOF){
> 		if(n>0){
> 			for(i=0;i<n;i++){
> 				scanf("%d%d%d%d",&r.x1,&r.y1,&r.x2,&r.y2);
> 				//分出横坐标
> 				tmap[i*2]=r.x1;
> 				tmap[i*2+1]=r.x2;
> 				//分出竖线
> 				v[i*2].in=1;
> 				v[i*2].x=r.x1;
> 				v[i*2].y1=r.y1;
> 				v[i*2].y2=r.y2;
> 				v[i*2+1].in=0;
> 				v[i*2+1].x=r.x2;
> 				v[i*2+1].y1=r.y1;
> 				v[i*2+1].y2=r.y2;
> 				//找出y的范围
> 				if(r.y1<miny)
> 					miny=r.y1;
> 				if(r.y2>maxy)
> 					maxy=r.y2;
> 			}
> 			
> 			qsort(tmap,n*2,sizeof(int),cmp);
> 			qsort(v,n*2,sizeof(vet),cmpv);
> 			//======================debug=================================
> 			for(i=0;i<2*n;i++){
> 				
> 				printf("%d\n",i);
> 				printf("%d %d %d %d\n",v[i].x,v[i].y1,v[i].y2,v[i].in);
> 				
> 			}
> 			//============================================================
> 			xmap[0]=tmap[0];
> 			for(i=1,j=0;i<2*n;i++){//得到去除了重复值的横坐标
> 				if(tmap[i]!=xmap[j]){
> 					j++;
> 					xmap[j]=tmap[i];
> 				}
> 			}
> 			nn=j+1;
> 			l=creatit(miny,maxy);
> 			lastm=0;
> 			lastline=0;
> 			for(i=0,j=0;i<nn;i++){//遍历每个横坐标
> 				for(;j<2*n;j++){//遍历该横坐标上的竖线
> 					if(v[j].x!=xmap[i])
> 						break;
> 					if(v[j].in==1)//插入线段
> 						insertit(l,v[j].y1,v[j].y2);
> 					if(v[j].in==0)//删除线段
> 						deleteit(l,v[j].y1,v[j].y2);
> 				}
> 				nowline=l->line;
> 				nowm=l->m;
> 				if(i!=nn-1)
> 				re+=((xmap[i+1]-xmap[i])*2*nowline);//不是最后一个，就把横向线段长度添加到结果里
> 				re+=abss(nowm-lastm);//添加竖向的线段长度
> 				lastm=nowm;
> 				lastline=nowline;
> 			}
> 		}
> 		printf("%d\n",re);
> 	}
> 	dropit(l);
> 	return 0;
> }
> 
> //=======================我过不了的数据===================================
> 
> 47
> -1105 -1155 -930 -285
> -765 -1115 -615 -375
> -705 -480 -165 -285
> -705 -1200 -175 -1025
> -275 -1105 -105 -385
> -10 -1165 185 -285
> 315 -1160 400 -710
> 340 -1195 655 -1070
> 580 -1140 655 -265
> 325 -480 395 -335
> 365 -390 620 -265
> 365 -770 610 -665
> 815 -1195 1110 -1070
> 825 -760 1100 -660
> 810 -405 1115 -275
> 780 -700 860 -360
> 1065 -695 1130 -360
> 775 -1110 860 -735
> 1070 -1110 1145 -730
> -1065 -95 140 260
> -725 80 750 460
> 135 -135 490 840
> 135 -135 490 750
> -520 40 -210 945
> -595 620 215 695
> 670 -5 855 610
> 550 -75 830 -25
> 815 240 1085 370
> 980 -90 1125 145
> 280 150 490 315
> -1035 -155 -845 -90
> 855 815 950 1030
> 785 980 860 1165
> 945 985 1015 1160
> 730 835 1075 895
> 875 695 935 790
> -1165 420 -520 650
> -1090 815 -210 945
> -130 800 65 1160
> 120 980 690 1150
> -1140 995 -125 1180
> -825 1050 -195 1135
> -90 865 10 1090
> 280 1045 625 1090
> -655 1065 -245 1115
> -1155 70 -790 315
> -1005 110 -825 225
> 
> 
> 我输出：36790
> 该输出：37000

Home Page Go Back To top