| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
c代码80行,仅供参考#include <stdio.h>
int main()
{
int i,t,w,h,j,k,n,l,f,y,z;
scanf("%d",&t);
int re[t+1];
for(f=1;f<=t;f++)
{
scanf("%d",&w);
scanf("%d",&h);
scanf("%d",&n);
int a[n+1],b[n+1],c[n+1],d[n+1];
for(j=1;j<=n;j++)
{
scanf("%d",&a[j]);
scanf("%d",&b[j]);
}
for(j=1;j<=n;j++)
{
scanf("%d",&c[j]);
scanf("%d",&d[j]);
}
int r[n+1],v[n+1];
for(k=1;k<=n;k++)
{
r[k]=k;
v[k]=k;
}
int p[n][n],q[n][n];
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
p[i][j]=(a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]);
q[i][j]=(c[i]-c[j])*(c[i]-c[j])+(d[i]-d[j])*(d[i]-d[j]);
if((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])==1)
{
if(r[j]==j) r[j]=r[i];
else if(r[j]!=j&&r[i]==i) r[i]=r[j];
else if(r[j]!=j&&r[i]!=i) {for(k=1;k<=n;k++) {if(r[k]==r[j]) r[k]=r[i]; }}
}
if((c[i]-c[j])*(c[i]-c[j])+(d[i]-d[j])*(d[i]-d[j])==1)
{
if(v[j]==j) v[j]=v[i];
else if(v[j]!=j&&v[i]==i) v[i]=v[j];
else if(v[j]!=j&&v[i]!=i) {for(k=1;k<=n;k++) {if(v[k]==v[j]) v[k]=v[i]; }}
}
}
}
int s[n+1],u[n+1];
for(k=1;k<=n;k++)
{s[k]=0;u[k]=0;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(r[i]==k&&r[j]==k) s[k]=s[k]+p[i][j];
if(v[i]==k&&v[j]==k) u[k]=u[k]+q[i][j];
}
}
}
for(j=1;j<n;j++)
{
for(i=1;i<=n-j;i++)
{
if(s[i]>s[i+1]) {y=s[i+1]; s[i+1]=s[i]; s[i]=y;}
if(u[i]>u[i+1]) {y=u[i+1]; u[i+1]=u[i]; u[i]=y;}
}
}
int count=0;
for(i=1;i<=n;i++)
{
if (s[i]==u[i]) count++;
}
if(count==n) re[f]=1; else re[f]=0;
}
for(i=1;i<=t;i++){ if(re[i]==1) printf("YES\n"); else printf("NO\n"); };
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator