1693.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
char set[100][100];
int n_cl,n_rl;
struct line
{int x1,x2,y1,y2;};

line c[100],r[100];
inline int min(int a,int b)
{if(a<b)return a;
else return b;
}
inline int max(int a,int b)
{if(a>b)return a;
else return b;
}



int jiao(line rl,line cl)
{return rl.x1<=cl.x1&&cl.x1<=rl.x2&&cl.y1<=rl.y1&&rl.y1<=cl.y2;}

int cs[100];
int rs[100];

int main()
{int i,j,k,n,t,a,b,cc,d;
long s,m;
cin>>t;
while(t--)
{cin>>n;n_cl=0;n_rl=0;
for(i=0;i<n;i++)
{cin>>a>>b>>cc>>d;
if(a==cc){c[n_cl].y1=min(b,d);c[n_cl].y2=max(b,d);c[n_cl].x1=c[n_cl].x2=a;n_cl++;}
else {r[n_rl].x1=min(a,cc);r[n_rl].x2=max(a,cc);r[n_rl].y1=r[n_rl].y2=b;n_rl++;}
}




for(i=0;i<n_cl;i++)
for(j=0;j<n_rl;j++)
if(jiao(r[j],c[i]))set[i][j]=1;else set[i][j]=0;

s=0;
for(i=0;i<n_cl;i++)
for(j=i+1;j<n_cl;j++)
{m=0;
for(k=0;k<n_rl;k++)
if(set[i][k]&&set[j][k])m++;
s+=m*(m-1)/2;
}
cout<<s<<endl;
}
return 0;
}