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

## Re:TLE~~~~~~~~~~~~How to do it?

Posted by bluetiger at 2006-04-07 18:27:07 on Problem 1389
In Reply To:TLE~~~~~~~~~~~~How to do it? Posted by:bluetiger at 2005-05-23 01:00:37
```线段树：）
> #include<stdio.h>
> #include<stdlib.h>
> #include<memory.h>
> int a[1001][4],x[2002],y[2002];
> inline int cmp(const void *a,const void *b)
> {
>     return *(int*)a-*(int*)b;
> }
> int main()
> {
>     //freopen("test.txt","r",stdin);
>     //freopen("out.txt","w",stdout);
>     int i,j,k,x1,y1,x2,y2,n,m,s;
>     while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2),x1!=-1&&x2!=-1&&y1!=-1&&y2!=-1)
>     {
>         n=0;s=0;
>         a[n][0]=x[n*2]=x1;a[n][1]=y[n*2]=y1;a[n][2]=x[n*2+1]=x2;a[n][3]=y[n*2+1]=y2;
>         n++;
>         while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2),x1!=-1&&x2!=-1&&y1!=-1&&y2!=-1)
>         {
>             a[n][0]=x[n*2]=x1;a[n][1]=y[n*2]=y1;a[n][2]=x[n*2+1]=x2;a[n][3]=y[n*2+1]=y2;
>             n++;
>         }
>         qsort(x,2*n,sizeof(x[0]),cmp);qsort(y,2*n,sizeof(y[0]),cmp);
>         //for(i=0;i<2*n;i++)printf("%d ",x[i]);printf("\n");
>         //for(i=0;i<2*n;i++)printf("%d ",y[i]);printf("\n");
>         for(i=1;i<2*n;i++)
>           if(x[i]>x[i-1])
>             for(j=1;j<2*n;j++)
>               if(y[j]>y[j-1])
>               {
>                   m=0;
>                   for(k=0;k<n;k++)
>                     if(x[i-1]>=a[k][0]&&x[i]<=a[k][2]&&y[j-1]>=a[k][1]&&y[j]<=a[k][3])
>                     {m=1;break;}
>                   if(m)s+=(x[i]-x[i-1])*(y[j]-y[j-1]);
>               }
>         printf("%d\n",s);
>     }
>     return 0;
> }
```

Followed by: