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 |
FT,总是Runtime ErrorRT #include<iostream> #include<algorithm> using namespace std; struct node { int l,r; bool cover; }; struct rec { double x1,x2,y1,y2; }; rec data[105]; double hash[210]; double hashx[210]; node tree[600]; int find_num(double x,int n) { int l=0; int r=n-1; int mid=(l+r)/2; while(x!=hash[mid]) { if(x>hash[mid]) l=mid+1; else r=mid-1; mid=(l+r)/2; } return mid; } void creat_tree(int l,int r,int p) { tree[p].l=l; tree[p].r=r; tree[p].cover=false; if(l+1<r) { int mid=(l+r)/2; creat_tree(l,mid,2*p); creat_tree(mid,r,2*p+1); } } void insert(int l,int r,int p) { // cout<<"insert:"<<l<<" "<<r<<" p="<<p<<endl; if(tree[p].l==l&&tree[p].r==r) { tree[p].cover=true; return; } int mid=(tree[p].l+tree[p].r)/2; if(tree[p].cover) { tree[2*p].cover=true; tree[2*p+1].cover=true; tree[p].cover=false; } if(l>=mid) { insert(l,r,2*p+1); return; } else if(r<=mid) { insert(l,r,2*p); return; } insert(l,mid,2*p); insert(mid,r,2*p+1); } double count(int p) { double sum=0; if(tree[p].cover) { sum=hash[tree[p].r]-hash[tree[p].l]; } else if(tree[p].l+1<tree[p].r) { sum=count(2*p)+count(2*p+1); } return sum; } int main() { int i,j,k,n,l,cnt=1; double sum; while(1) { scanf("%d",&n); if(n==0) break; for(i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&data[i].x1,&data[i].y1,&data[i].x2,&data[i].y2); hash[2*i]=data[i].y1; hash[2*i+1]=data[i].y2; hashx[2*i]=data[i].x1; hashx[2*i+1]=data[i].x2; } sort(hash,hash+2*n); sort(hashx,hashx+2*n); k=1; for(i=1;i<2*n;i++) { if(hash[i]==hash[i-1]) continue; hash[k++]=hash[i]; } l=1; for(i=1;i<2*n;i++) { if(hashx[i]==hashx[i-1]) continue; hashx[l++]=hashx[i]; } sum=0; for(i=0;i<l-1;i++) { creat_tree(0,l,1); for(j=0;j<n;j++) { if(data[j].x1<=hashx[i]&&data[j].x2>=hashx[i+1]) { int l=find_num(data[j].y1,k); int r=find_num(data[j].y2,k); insert(l,r,1); } } sum+=count(1)*(hashx[i+1]-hashx[i]); } printf("Test case #%d\n",cnt++); printf("Total explored area: %.2lf\n\n",sum); } //system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator