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 |
数据蒟蒻~直接暴力AC~#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; struct D { int x,y,z; }d[250]; int n; bool vis[250]; inline bool cmp(const D &a,const D &b) { return a.x>b.x; } void read() { for(int i=1;i<=n+n;i++) scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].z); sort(d+1,d+1+n+n,cmp); d[0].x=d[0].y=0x3f3f3f3f;d[0].z=0; } bool dfs(int u,int p1,int p2,int k1,int k2) { //printf("%d %d %d %d\n",p1,k1,p2,k2); if(k1>n||k2>n) return false; if(u==n+n+1) return true; if(d[p1].x-d[u].x>=d[p1].z+d[p1].z&&d[p1].y-d[u].y>=d[p1].z+d[p1].z) { vis[u]=1; if(dfs(u+1,u,p2,k1+1,k2)) return true; vis[u]=0; } if(d[p2].x-d[u].x>=d[p2].z+d[p2].z&&d[p2].y-d[u].y>=d[p2].z+d[p2].z) if(dfs(u+1,p1,u,k1,k2+1)) return true; return false; } void go() { memset(vis,0,sizeof vis); vis[1]=1; dfs(2,1,0,1,0);//强制把1放在①里 for(int i=1;i<=n+n;i++) if(vis[i]) printf("%d %d %d\n",d[i].x,d[i].y,d[i].z); printf("-\n"); for(int i=1;i<=n+n;i++) if(!vis[i]) printf("%d %d %d\n",d[i].x,d[i].y,d[i].z); printf("\n"); } int main() { while(scanf("%d",&n),n) { read(); go(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator