sorting slides.txt

以前ACM在哈工程HRBEU做的一些简单题目

#include <iostream>
using namespace std;
bool pd[30][30],dp[30][30];
bool p[30],d[30];
struct pp
{
       int x1,x2,y1,y2;
}point[30];
int main()
{
    int n,n1,i,j,k,t1,t2,a1,a2,z[30],g;
    bool f,l;
    cin>>n;
    for(g=1;g<=n;g++)
    {
       cin>>n1;
       for(i=0;i<n1;i++)cin>>point[i].x1>>point[i].x2>>point[i].y1>>point[i].y2;
       for(i=0;i<n1;i++)
       {
          int x,y;
          cin>>x>>y;
          for(j=0;j<n1;j++)
          if(point[j].x1<x&&point[j].x2>x&&point[j].y1<y&&point[j].y2>y)
          {pd[i][j]=1;dp[j][i]=1;}
          else {pd[i][j]=0;dp[j][i]=0;}
       } 
       memset(p,1,n1);
       memset(d,1,n1);
       memset(z,0,sizeof(z));
       f=true;
       for(i=0;i<n1;i++)
    {
       for(j=0;j<n1;j++)
       {
        if(p[j])               
        {
        t1=0;
        for(k=0;k<n1;k++)
        if(d[k]&&pd[j][k]){t1++;a1=k;}
        if(t1==1){f=false;d[a1]=0;p[j]=0;z[a1]=j+1;break;}
        }
       if(d[j])               
        {
        t2=0;
        for(k=0;k<n1;k++)
        if(p[k]&&dp[j][k]){t2++;a2=k;}
        if(t2==1){f=false;p[a2]=0;d[j]=0;z[j]=a2+1;break;}
        }
       }  
   }
   cout<<"Heap "<<g<<endl;
   if(f)cout<<"None";
   else
   {
       l=false;
       for(i=0;i<n1;i++)
       {
          if(z[i]!=0)
          {
          char c='A'+i;
          if(l)cout<<" ";
          cout<<"("<<c<<","<<z[i]<<")";
          l=true;
          }
          
       }
   }
   cout<<endl<<endl;
 }
 return 0;
}