#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int b[82][82];
int bn[82][82],n;
struct Node
{
 int x;
 int y;
}node[82];
int fun(const void*a,const void*b)
{
 Node p,q;
 p=*(Node*)a,q=*(Node*)b;
 if(p.y!=q.y)return p.y-q.y;
 return p.x-q.x;
}
int find(int l)
{
    int i,j,k,p,sum=0;
    for(i=0;i<l-1;i++)
    {
        memset(bn,0,sizeof(bn));
        for(j=0;j<n;j++)
        {
            for(k=0;k<n;k++)
            {
                for(p=0;p<n;p++)
                  bn[j][k]+=b[j][p]*b[p][k];
            }    
        }    
        for(j=0;j<n;j++)
        for(k=0;k<n;k++)
        b[j][k]=bn[j][k];
    }    
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        sum+=b[i][j];   
    return sum;
}    

int main()
{
 int i,j,k,m,max,t,ans,count;
 while(scanf("%d",&n)!=EOF)
 {memset(b,0,sizeof(b));
  for(i=0;i<n;i++)
  {
   scanf("%d%d",&node[i].x,&node[i].y);
   if(node[i].x>node[i].y)
   {
   t=node[i].x,node[i].x=node[i].y,node[i].y=t;
   }
  }
  qsort(node,n,sizeof(node[0]),fun);
  for(i=0;i<n;i++)
  printf("%d %d\n",node[i].x,node[i].y);
  ans=1;t=node[0].y;
  for(i=1;i<n;i++)
  {
   if(node[i].x>=t)
   {
    ans++,t=node[i].y;
   }
  }
  for(i=0;i<n;i++)
          for(j=0;j<n;j++)
            if(node[i].y<=node[j].x)b[i][j]=1;   

  max=n-ans;//ans为不相交的总数 
  count=ans-1;
  ans=find(count);
  if(max==0)printf("0 1\n");
  else printf("%d %d\n",max,ans);
 }
}

• G++WA,C++TLE,ft?????????????????????????????????????????????? (1620) ecjtubaowp 2007-05-21 22:28:56