| ||||||||||
| 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