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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:数据全过了还是WA的看看

Posted by 1037053980 at 2018-07-31 16:11:14 on Problem 1328
In Reply To:Re:数据全过了还是WA的看看 Posted by:1904698024 at 2017-05-26 20:47:16
#include<stdio.h>
#include<math.h>
#include<String.h>
int D,n,gey=0;
int mark[1000], x[1000],y[1000],x0[1000],y00[1000],mark2[1000];
int leidaX[1000];
int Count;


int main(void)
{
	int number=1;
	while(scanf("%d %d",&n,&D),!(n==0&&D==0))
	{
		int j,a,bn=1;
		double kuo;//当前雷达坐标
		int i,k,l,temp;
		a=n-1;
		j=a;
		Count=0;
		gey=0;
		memset(mark,0,sizeof(int)*1000);
		memset(x,0,sizeof(int)*1000);
		memset(y,0,sizeof(int)*1000);
		memset(x0,0,sizeof(int)*1000);
		memset(y00,0,sizeof(int)*1000);
		memset(mark2,0,sizeof(int)*1000);
		while(n--) 
		{
			scanf("%d %d",&x[a-n],&y[a-n]);
			if(y[a-n]==D)
			{
				mark[a-n]=1;  //标记y=D的点
				leidaX[gey]=x[a-n];//记录雷达坐标 
				Count++;
				gey++;
			 } 
			 else if(y[a-n]>D||y[a-n]<0||D<=0) 
			 {
			 	bn=0;
			 }
		}
		if(bn)
		{
			int kk,GG,MM,lpl;
			a+=1;
			n+=1;
			//雷达数组查重 
			for(GG=0;GG<gey;GG++)
			{
				for(MM=GG+1;MM<gey;MM++)
				{
					if(leidaX[GG]>leidaX[MM])
					{
						lpl=leidaX[GG];
						leidaX[GG]=leidaX[MM];
						leidaX[MM]=lpl;
					}
				}
			}
			lpl=0;
			for(GG=1;GG<gey;GG++) 
			{
				if(leidaX[GG]==leidaX[GG-1])
				{
					lpl+=1;
				}
			}
			if(lpl!=0) Count=Count-lpl;
			gey-=1;
			for(;gey>=0;gey--)
			{
				for(kk=n;kk<a;kk++)
				{
					if(mark[kk]==1) continue;
					if((x[kk]-leidaX[gey])*(x[kk]-leidaX[gey])+y[kk]*y[kk]<=D*D) mark[kk]=1;
				}
			}
			gey=0;
			//将剩下的岛屿坐标抽出来 
			for(i=0;i<a;i++)
			{
				if(mark[i]!=1)
				{
					x0[gey]=x[i];
					y00[gey]=y[i];
					gey++;
				}
			}
		
			//将剩下的岛屿坐标排序 
			for(k=0;k<gey-1;k++)
			{
				for(l=k+1;l<gey;l++)
				{
					if(x0[k]>x0[l])
					{
						temp=x0[k];
						x0[k]=x0[l];
						x0[l]=temp;
					}
				}
			}
			
			//坐标更新部分 
			a=0;
			j=0;
			while(gey>0&&mark2[gey-1]!=1)
			{
				kuo=(double)x0[a]+sqrt(D*D-y00[a]*y00[a]);
				for(;x0[j]<=kuo&&j<gey;j++)
				{
					if((x0[j]-kuo)*(x0[j]-kuo)+y00[j]*y00[j]>D*D)
					{
						a+=1;
						kuo=(double)x0[a]-sqrt(D*D-y00[a]*y00[a]);
						}
						mark2[j]=1;		
				}
				
				while(j<gey&&x0[j]<=kuo+D)
				{
					
					if((x0[j]-kuo)*(x0[j]-kuo)+y00[j]*y00[j]<=D*D)
					{
						mark2[j]=1;
						
					}
					j++;
				}
				a=j;
				Count+=1;
			}
			printf("Case %d: %d\n",number,Count);
		}
		else 
		{
			printf("Case %d: -1\n",number);
		}
		number+=1;
	}
	

}

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