好贷网好贷款

HDU 4739 Zhuge Liang's Mines

发布时间:2016-12-3 4:00:12 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4739 Zhuge Liang's Mines",主要涉及到HDU 4739 Zhuge Liang's Mines方面的内容,对于HDU 4739 Zhuge Liang's Mines感兴趣的同学可以参考一下。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4739 这次网络赛的一个简单题,我没出,坑了队友 其实思路是对的,但是比较乱,也没想到是背包,结束之后接着按照原先的思路去做竟然AC了! 先暴力找出所有正方形,然后寻找其中点不相交且正方形最多的以个子集,由于最多就是五个,所以直接for循环了! #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> using namespace std; #define maxn 30 #define MAX(a,b) (a>b?a:b) struct point{ double x,y; }po[maxn]; bool is_visit[maxn]; struct node{ int a,b,c,d; }no[maxn*maxn*maxn*maxn]; int n,sum; int fun(int i,int j,int x,int y) { if(po[i].x==po[j].x&&po[j].x==po[x].x) return 0; if(po[i].y==po[j].y&&po[j].y==po[x].y) return 0; if(po[i].x!=po[j].x||po[x].x!=po[y].x) return 0; if(po[i].y!=po[x].y||po[j].y!=po[y].y) return 0; if(po[j].y-po[i].y!=po[x].x-po[i].x) return 0; else return 1; } bool cmp(const point &a,const point &b){ if(a.x!=b.x) return a.x < b.x; return a.y < b.y; } int main(){ int i,j,k,p,q,r,t,ans; while(scanf("%d",&n)!=EOF){ if(n==-1) return 0; for(i=0;i<n;i++) scanf("%lf%lf",&po[i].x,&po[i].y); sort(po,po+n,cmp); sum=0; ans=0; for(i=0;i<n;i++) for(j=i+1;j<n;j++) for(k=j+1;k<n;k++) for(p=k+1;p<n;p++){ if(fun(i,j,k,p)) no[sum].a=i,no[sum].b=j,no[sum].c=k,no[sum++].d=p; } for(i=0;i<sum;i++){ memset(is_visit,true,sizeof(is_visit));ans=MAX(ans,1); is_visit[no[i].a]=is_visit[no[i].b]=is_visit[no[i].c]=is_visit[no[i].d]=false; for(j=i+1;j<sum;j++){ if(is_visit[no[j].a] && is_visit[no[j].b] &&is_visit[no[j].c] &&is_visit[no[j].d]) is_visit[no[j].a]=is_visit[no[j].b]=is_visit[no[j].c]=is_visit[no[j].d]=false,ans=MAX(ans,2); else continue; for(k=j+1;k<sum;k++){ if(is_visit[no[k].a] && is_visit[no[k].b] &&is_visit[no[k].c] &&is_visit[no[k].d]) is_visit[no[k].a]=is_visit[no[k].b]=is_visit[no[k].c]=is_visit[no[k].d]=false,ans=MAX(ans,3); else continue; for(p=k+1;p<sum;p++){ if(is_visit[no[p].a] && is_visit[no[p].b] &&is_visit[no[p].c] &&is_visit[no[p].d]) is_visit[no[p].a]=is_visit[no[p].b]=is_visit[no[p].c]=is_visit[no[p].d]=false,ans=MAX(ans,4); else continue; for(q=p+1;q<sum;q++){ if(is_visit[no[q].a] && is_visit[no[q].b] &&is_visit[no[q].c] &&is_visit[no[q].d]) {ans=MAX(ans,5);break;} } is_visit[no[p].a]=is_visit[no[p].b]=is_visit[no[p].c]=is_visit[no[p].d]=true; } is_visit[no[k].a]=is_visit[no[k].b]=is_visit[no[k].c]=is_visit[no[k].d]=true; } is_visit[no[j].a]=is_visit[no[j].b]=is_visit[no[j].c]=is_visit[no[j].d]=true; } } printf("%d\n",ans*4); } return 0; }

上一篇:雄才、大略、贪婪、恐惧
下一篇:如何才能快乐?

相关文章

相关评论