注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【搜索】Codeforces #97 DIV2 D Rectangle and Square  

2011-12-13 10:34:50|  分类: ACM_搜索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
题目大意:
给出8个点的坐标,将这8个点分为两组,每组4个点,使得第一组的4各点构成正方形,第二组的4个点构成长方形(包含正方形)

分析:
简单搜索,关键是要在很短的时间内写出代码,刚开始写的时候我是按照DFS写的,代码很长,后来看了教主的代码,感觉教主不愧为教主,代码十分好看,简洁,

一下代码是看了教主代码后自己稍微改了一下,便于理解

因为数据量比较小,教主在搜索的时候是用一个set进行状态压缩,用循环代替了DFS

代码:
#include <cstdio> 
#include <cstring>
#include <algorithm>
#define two(X) (1<<(X))// 2 ^ X
#define contains(S,X) (((S)&two(X))!= 0 )//判断10进制数S中的2进制表示中,第X位是否是1

using namespace std;
int sx[8],sy[8];

int countbit(int n)// 计算一个10进制数的2进制表示中有几个1
{
       return n == 0 ? 0 : (1 + countbit(n & (n-1)));
}

int sqr(int x)
{
       return (x) * (x);
}

void init()
{
       for(int i = 0;i < 8;i ++)
       {
              scanf("%d%d",&sx[i],&sy[i]);
       }
}

int dist2(int x1,int y1,int x2,int y2)
{
       return sqr(x1 - x2) + sqr(y1 - y2);
}

bool ck2(int cx[],int cy[],bool sp)
{
       if(dist2(cx[0],cy[0],cx[1],cy[1]) != dist2(cx[2],cy[2],cx[3],cy[3]))
              return false;
       if(dist2(cx[0],cy[0],cx[3],cy[3]) != dist2(cx[1],cy[1],cx[2],cy[2]))
              return false;
       if(dist2(cx[0],cy[0],cx[1],cy[1]) + dist2(cx[1],cy[1],cx[2],cy[2]) 
              != dist2(cx[0],cy[0],cx[2],cy[2]))
              return false;
       if(sp && dist2(cx[0],cy[0],cx[1],cy[1]) != dist2(cx[1],cy[1],cx[2],cy[2]))
              return false;
       return true;
}


bool ck(int cx[],int cy[],bool sp)
{
       int p[4];
       for(int i = 0;i < 4;i ++) p[i] = i;
       do
       {
              int x[4],y[4];
              for(int i = 0;i < 4;i ++) x[i] = cx[p[i]],y[i] = cy[p[i]];
              if(ck2(x,y,sp)) return true;

       }while(next_permutation(p,p+4));//全排列
       return false;

}


void work()
{
       for(int set = 0;set < two(8);set ++) if(countbit(set) == 4)//set作为状态集,set的2进制表示中第i位为1表示第i个坐标分到第1组
       {
              int x1[4],y1[4],x2[4],y2[4];
              int c1 = 0,c2 = 0;
              for(int i = 0;i < 8;i ++)
              {
                     if(contains(set,i))
                            x1[c1] = sx[i],y1[c1++] = sy[i];
                     else
                            x2[c2] = sx[i],y2[c2++] = sy[i];
              }
              
              if(ck(x1,y1,true) && ck(x2,y2,false))
              {
                     printf("YES\n");
                     for(int i = 0;i < 8;i ++) if(contains(set,i))
                            printf("%d ",i + 1);
                     printf("\n");
                     for(int i = 0;i < 8;i ++) if(!contains(set,i))
                            printf("%d ",i + 1);
                     printf("\n");
                     return ;
              }
       }
       printf("NO\n");
}

int main()
{
       init();
       work();
}

  评论这张
 
阅读(129)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018