枚举三个需要调整位置的皇后,调整后只有两种情况,分别判断是否符合要求
1 #include <iostream>
2 using namespace std;
3 int n;
4 int p[55][2];
5 int he[55],cha[55];
6 bool v[55];
7
8 bool ok(int x,int y,int d){
9 bool re=true;
10 int ch=x-y;
11 for (int i=1;i<=n+3;++i) if (!v[i]&&i!=n+d){
12 if ((x+y==he[i])||(cha[i]==ch)){
13 re=false;
14 break;
15 }
16 }
17 return re;
18 }
19
20 int main(){
21 scanf("%d",&n);
22 for (int i=1;i<=n;++i){
23 scanf("%d %d",&p[i][0],&p[i][1]);
24 he[i]=p[i][0]+p[i][1];
25 cha[i]=p[i][0]-p[i][1];
26 }
27 int ans=0;
28 for (int i=1;i<=n;++i)
29 for (int j=i+1;j<=n;++j)
30 for (int k=j+1;k<=n;++k){
31 v[i]=true;
32 v[j]=true;
33 v[k]=true;
34
35 int x1=p[i][0],x2=p[j][0],x3=p[k][0];
36 int y1=p[j][1],y2=p[k][1],y3=p[i][1];
37 he[n+1]=x1+y1; cha[n+1]=x1-y1;
38 he[n+2]=x2+y2; cha[n+2]=x2-y2;
39 he[n+3]=x3+y3; cha[n+3]=x3-y3;
40 if (ok(x1,y1,1)&&ok(x2,y2,2)&&ok(x3,y3,3)) ++ans;
41
42 x1=p[i][0],x2=p[j][0],x3=p[k][0];
43 y1=p[k][1],y2=p[i][1],y3=p[j][1];
44 he[n+1]=x1+y1; cha[n+1]=x1-y1;
45 he[n+2]=x2+y2; cha[n+2]=x2-y2;
46 he[n+3]=x3+y3; cha[n+3]=x3-y3;
47 if (ok(x1,y1,1)&&ok(x2,y2,2)&&ok(x3,y3,3)) ++ans;
48
49 v[i]=false;
50 v[j]=false;
51 v[k]=false;
52 }
53 cout<<ans;
54 }
55
posted on 2008-11-05 17:16
Joseph 阅读(124)
评论(0) 编辑 收藏 引用