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

求DaLao指点,贴代码

Posted by pojpxa at 2019-02-15 17:01:42 on Problem 1328
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int Max=1010;
struct dao
{
	double st;
	double ed;
}b[Max];
bool f[Max];

void Qsort(int l,int r)
{
	int i,j;
	dao x,temp;
	i=l;
	j=r;
	x=b[(l+r)/2];
	while(i<=j)
	{
		while(x.ed>b[i].ed||(x.ed==b[i].ed&&x.st>b[i].st))	i++;
		while(x.ed<b[j].ed||(x.ed==b[j].ed&&x.st<b[j].st))	j--;
		if(i<=j)
		{
			temp=b[i];
			b[i]=b[j];
			b[j]=temp;
			i++;
			j--;
		}
	}
	if(i<r)	Qsort(i,r);
	if(l<j)	Qsort(l,j);
}

int main()
{
	int n,d;
	double x,y;
	int res=0;
	double s;
	bool fff=false;
	int iii=0;
	while(1)
	{
		iii++;
		scanf("%d%d",&n,&d);
		if(!n&&!d)	break;
		for(int i=1; i<=n; i++)
		{
			scanf("%lf%lf",&x,&y);
			if(y>d)	fff=true;
			b[i].st=x-sqrt(d*d-y*y);
			b[i].ed=x+sqrt(d*d-y*y);
			f[i]=false;
		}
		if(fff)
		{
			printf("Case %d: -1\n",iii);
			break;
		}
		Qsort(1,n);
		res=0;
		for(int i=1; i<=n; i++)
		{
			if(!f[i])
			{
				f[i]=true;	res++;
				for(int j=i+1; j<=n; j++)
					if(!f[j]&&b[j].st<=b[i].ed)
						f[j]=true;
			}
		}
		printf("Case %d: %d\n",iii,res);
	}
	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