10382 - Watering Grass

[Jan]

I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:

Code: Select all

12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2

Output:

Code: Select all

-1

Hope it helps.

[Terro]

I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:

Code: Select all

12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2

Output:

Code: Select all

-1

Hope it helps.

Thanks a lot.
I've modified my program. And I didn't get RE. But after modifying, I got WA. Here is my new program

Code: Select all

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

struct node
{
	double begin, end;
} section[10001];

inline int cmp(const void* a, const void* b)
{
	return ((node*)a)->begin > ((node*)b)->begin ? 1 : -1;
}

int main()
{
	int n, l, w, r, pos;
	while (cin >> n)
	{
		cin >> l >> w;
		double w2 = double(w*w)/4;
		for (int i = 1; i <= n; i++)
		{
			cin >> pos >> r;
			double tmp = sqrt(r*r-w2>0 ? r*r-w2 : 0);
			section[i].begin = pos - tmp;
			section[i].end = pos + tmp;
		}
		qsort(&section[1], n, sizeof(node), cmp);
		double st = 0;
		int count = 0, p = 0;
		if (section[1].begin > 0 || n <= 0 || w <= 0 || l <= 0)
		{
			cout << "-1\n";
			st = l;
			count = -1;
		}
		while (st < l)
		{
			double tmpmax = 0;
			int maxi = p;
			int pre = maxi;	//In order to check wheather it's able to find the next section
			while (section[++p].begin - st < 1e-8 && p <= n)
				if (section[p].end - st > tmpmax)
				{
					tmpmax = section[p].end - st;
					maxi = p;
				}
			if (maxi == pre)
			{
				cout << "-1\n";
				st = l;
				count = -1;
			}
			else
			{
				st = section[maxi].end;
				count++;
			}
		}
		if (count > 0)
			cout << count << endl;
	}
	return 0;
}

[Jan]

Try the cases.

Input:

Code: Select all

2 26 6
4 10
16 14
10 6 37
20 4
19 20
19 2
8 4
7 19
7 14
3 17
1 19
18 1
15 19

Output:

Code: Select all

2
2

Hope these help.

[Terro]

Try the cases.

Input:

Code: Select all

2 26 6
4 10
16 14
10 6 37
20 4
19 20
19 2
8 4
7 19
7 14
3 17
1 19
18 1
15 19

Output:

Code: Select all

2
2

Hope these help.

Really thanks for your datas. It just helped me find a mistake. But I still get WA. I've been very confused. Could you please give me some advice? Thanks a lot.

[Jan]

Check the following files...

Input
Ouput
Hope these help.

[Tirdad]

Jan said:
I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:
Code:
12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2

Output:
Code:
-1

I checked this test case too and it produced the correct output with my binary. now I guess that there might be some coflicts with the compilers.
I use VS2005 but in near future I switch to a better substitude!
can you tell me what is your IDE and compiler Jan?
by the way I cheched the input and output file that you upload and unfortunatly the code is still correct!

[Jan]

My compiler is MS visual studio 6.0. Its hard to generate effective cases for geometry problems. The random cases matched! Thats why I had to check your coe manually. But couldnt figure out the error.

[Terro]

Check the following files...

Input
Ouput
Hope these help.

I've been really confused. I checked my program using these datas just now. It worked well. But I still got a WA.
So what should I exactly do?

[Jan]

There can be precision errors. For floating point numbers you should use the comparisons as follows:

Code: Select all

 int	   double
a == b	fabs(a-b) < eps
a != b	fabs(a-b) > eps
a > b	 a > b + eps
a < b	 a + eps < b

Here 'eps' is a small value. Its better to set 'eps' from 10^(-7) to 10^(-11). Hope it works.

[Leonid]

I'm reaaaaaly confused why I can get AC for this task.
1. I've passed sample cases
2. I've passed all test cases on the board
3. I've passed around 4000 randomly generated test cases verified with http://www.uvatoolkit.com
4. I've found that the problem contains such values with l == 0 or w == 0 and I suspect that the answer for the test cases snould be 0, while the answers produced by http://www.uvatoolkit.com does not follow this logic.
5. I've tried to change EPS value to 1e-7, 1e-11, 1e-13 but still WA
6. WHAT A F*** HAVE I MISSED OUT? When I look at the code I don't feel that there are many mistakes to do so I'm asking for your help guys, please find my mistake!

Code: Select all

const double EPS = 1e-11;
typedef pair<double, double> pii;
bool solve() {
	int n, l, w;
	if (scanf("%d %d %d ",&n,&l,&w) != 3)
		return false;

	vector<pii> sprinklers;
	for (int i = 0; i < n; i++) {
		int p, r;
		scanf("%d %d ",&p,&r);
		pii pd;
		if (2 * r > w) {
			double d = sqrt(r * r - (w * w) / 4.0);
			pd.first = p - d;
			pd.second = p + d;
			sprinklers.push_back(pd);
		}
	}
	sort(sprinklers.begin(), sprinklers.end());
	int m = SZ(sprinklers);
	
	double start = 0;
	int j = 0, total = 0, pj = 0;
	while (start < (double)l - EPS) {
		double go = start;
		while (j < m && sprinklers[j].first - EPS < start) {
			go = max(go, sprinklers[j].second);
			j++;
		}
		if (pj == j) {
			printf("-1\n");
			return true;
		}
		pj = j;
		start = go;
		total++;
	}
	printf("%d\n", total);

	return true;
}

[Sanik]

For those who have got an WA, this may be the problem you are facing,
I've finally found why I couldn't get an AC after testing all the test cases others have posted(which were all correct).
But I still can't figure out why it is caused ....

At somewhere in my code I wrote

Code: Select all

double length_2 = sqrt((double)(rad*rad)-w2_2);

and got a WA

But when I changed it to

Code: Select all

double length_2 = sqrt((double)rad*rad-w2_2);

I got an AC

But to my knowledge it should be the same(even safer to give a bracket)

Can anybody tell me why??
-------
I've found out why....because it may overflow.... if I used (double)rad*rad

[ACslow]

Code: Select all

var p,pi,t,len,n,w,i,tot:longint;
    l,r:array[0..10000]of double;
    now,max:double;
    flag:boolean;
procedure qsort(x,y:longint);
  var i,j:longint;
      k,temp:double;
  begin
    i:=x;j:=y;k:=l[(i+j) div 2];
    repeat
      while l[i]<k do inc(i);
      while l[j]>k do dec(j);
      if not (i>j) then begin
        temp:=l[i];l[i]:=l[j];l[j]:=temp;
        temp:=r[i];r[i]:=r[j];r[j]:=temp;
        inc(i);dec(j);
      end;
    until i>j;
    if x<j then qsort(x,j);
    if i<y then qsort(i,y);
  end;

begin
  while not eof do begin
    readln(n,len,w);
    t:=0;
    for i:=1 to n do begin
      readln(p,pi);
      if pi>w/2 then begin
        inc(t);
        l[t]:=p-sqrt(sqr(pi)-sqr(w/2));
        if l[t]<0 then l[t]:=0;
        r[t]:=p+sqrt(sqr(pi)-sqr(w/2));
        if r[t]>len then r[t]:=len;
        //writeln(l[t],' ',r[t]);
      end;
    end;
    qsort(1,t);
    now:=0;
    i:=1;
    tot:=0;
    flag:=true;
    while now<len do begin
      max:=0;
      while (l[i]<=now) and (i<=t) do begin
        if r[i]>max then max:=r[i];
        inc(i);
      end;
      if max=0 then begin
        writeln(-1);
        flag:=false;
        break;
      end;
      now:=max;
      inc(tot);
    end;
    if flag then writeln(tot);
  end;
end.

I test many cases,and it's no problem.But online-judge says "runtime error".I check the program over and over again,but i still can not find any mistake.could you help me?

[AhmadKhatar]

Hi!
I checked the code several times but I can't find any mistake in it. Does anybody know the problem with it?
Here is my code:

Code: Select all

#include <iostream>
#include <cmath>

using namespace std;

int n;
int sX [ 10000 ], sR [ 10000 ];
int l, w;
struct Line
{
	double l, r;
} ln [ 10000 ];

void process();
void construct();

int main()
{
	while ( cin >> n >> l >> w )
	{
		for ( int i = 0; i < n; i++ )
		{
			cin >> sX[ i ] >> sR[ i ];
		}
		process();
	}

	return 0;
}

void process()
{
	construct();

	double cV;
	cV = 0;
	
	Line tLn [ 10000 ];
	int tNo;

	int cnt = 0;
	while ( cV < l && n > 0 )
	{
		int next = -1;
		for ( int i = 0; i < n; i++ )
		{
			if ( next == -1 )
			{
				next = i;
			}
			else if ( (ln[ i ].l < ln[ next ].l) ||
				       (ln[ i ].l == ln[ next ].l && ln[ i ].r > ln[ next ].r) )
			{
				next = i;
			}
		}
		
		if ( ln[ next ].l > cV )
		{
			cout << -1 << endl;
			return;
		}
		cV = ln[ next ].r;
		cnt++;

		tNo = 0; // refresh
		for ( int j = 0; j < n; j++ )
		{
			if ( ln[ j ].l < cV )
			{
				if ( ln[ j ].r <= cV )
				{
					// do nothing
				}
				else
				{
					ln[ j ].l = cV;
					tLn[ tNo++ ] = ln[ j ];
				}
			}
			else
			{
				tLn[ tNo++ ] = ln[ j ];
			}
		}

		for ( int j = 0; j < tNo; j++ )
		{
			ln[ j ] = tLn[ j ];
		}
		n = tNo;
	}

	if ( cV < l )
	{
		cout << -1 << endl;
	}
	else
	{
		cout << cnt << endl;
	}
}

void construct()
{
	double tL, tR;
	int tCnt = 0;
	for ( int i = 0; i < n; i++ )
	{
		if ( sR[ i ] > w / 2.0 )
		{
			tL = max( sX[ i ] - sqrt( 4 * sR[ i ] * sR[ i ] - w * w + 0.0 ) / 2.0 , 0.0 );
			tR = min( sX[ i ] + sqrt( 4 * sR[ i ] * sR[ i ] - w * w + 0.0 ) / 2.0 , l + 0.0 );
			ln[ tCnt ].l = tL;
			ln[ tCnt ].r = tR;
			tCnt++;
		}
	}
	n = tCnt;
}

Thanks in advance!

[brianfry713]

You're having the same issue as Sanik in the post above yours. There's probably a case like:

Code: Select all

1 1000000001 100
1000000000 1000000000

[AhmadKhatar]

Many Thanks!
I got AC!