| ||||||||||
| 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