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

测过很多组数据了 可是还是一直WA 过了的朋友们帮忙看看 精度应该没有问题

Posted by alpc12 at 2006-12-07 00:59:51 on Problem 1328
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

//const int MAXINT = 100000000;
//const double INF = 10e100;
//const double EPS = 10e-6;
const int maxn = 1010;
struct Line{double s, e;}l[maxn];
bool tag[maxn];

int ni, dis;
int tc;
int ans;

int cmp(const void * a, const void * b)
{
	return ((*(Line *)a).s > (*(Line *)b).s) ? 1 : -1;
}

inline double len(int x, int y, double& x2)
{
	x2 = x*1.0+sqrt(dis*dis-y*y);
	return x*1.0-sqrt(dis*dis-y*y);
}

void init()
{
	int i, x, y;
	//initiation
	memset(l, 0, sizeof(l));
	memset(tag, false, sizeof(tag));
	ans = 0;
	//input
	for(i=0; i<ni; i++)
	{
		scanf("%d%d", &x, &y);
		if(y>dis) {ans = -1; return;}
		l[i].s = len(x, y, l[i].e);
	}
	qsort(l, ni, sizeof(Line), cmp);
}

void work()
{
	int i = 0, j;
	if(ans != -1)
	{
		for(i=0; i<ni; i++)
			if(!tag[i])
			{
				for(j=i+1; j<ni; j++)
				{
//相交
					if(l[j].s <= l[i].e && l[j].e >l[i].e) tag[j] = true; 
//包含	
				          if(l[j].e <= l[i].e) tag[i] = true;
				}
				if(!tag[i])	ans++;
			}
	}
	printf("Case %d: %d\n", tc, ans);
}

int main()
{
//	freopen("t.in", "r", stdin);
	while(scanf("%d%d", &ni, &dis), ni>0)
	{
		tc++;
		init();
		work();
	}
	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