Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

数据蒟蒻~直接暴力AC~

Posted by proverbs at 2012-09-22 21:48:35 on Problem 2303
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator