Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

FT,总是Runtime Error

Posted by rcrt10 at 2009-08-13 17:09:19 on Problem 1151
RT
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator