11096 - Nails

[helloneo]

Because the problem statements say..

what will be the final length of the rubber ribbon after surrounding the nails

[AxM]

hahaha what a stupid mistake...

I need more I/O !

[sapnil]

Try This Case

Code: Select all

Input:
1000000
999999
99999
9999
999
9
1
0
2
3

Output:
1024000
1222221
299997
29997
2997
27
Not Exist!
Not Exist!
4
9

Thanks
Keep posting
Sapnil
SUST

[Ildrial]

This exercise is making me (and a friend of mine) crazy!

We both developed the exercise independently and have the same problems: Wrong Answer!

Of course, we tested for many cases and always seemed to get the right answers. (if we didn't make some errors in our calculation by hand)

In addition to the few test cases that were already postet, we both got the following results:

19
5 7
0 1
0 2
0 3
2 1
2 2
2 3
1 4

1 1
1 10

0 1
0 0

2 1
0 1

4 4
0 0
1 1
2 0
1 -1

3 3
0 0
1 1
2 0

1 6
0 0
0 1
0 2
1 2
1 1
1 0

1 2
0 1
0 2

2 4
0 0
3 1
2 4
-1 3

2 9
0 0
100 100
200 0
100 -100
20 1
34 5
50 9
55 -8
101 100

4 4
0 0
1 1
2 0
1 -1

1 6
0 1
0 2
1 2
1 1
1 0
0 0

2 4
0 0
0 1
1 0
1 1

5 4
0 0
0 1

1 0
1 1

1 2
1 0
2 0

1 3
1 0
2 0
3 0

2 4
0 0
0 1
1 0
1 1

5 4
0 0
0 1
1 0
1 1

1 27
0 2
0 1
0 0
0 -1
1 -2
1 -1
1 0
1 1
1 2
2 1
2 0
2 -1
3 -1
2 -2
3 -2
2 -3
3 -3
-1 2
-1 1
-1 0
-1 -1
-1 -2
-2 -2
-2 -1
-2 0
-2 1
-3 0

8.82843
1.00000
0.00000
2.00000
5.65685
4.82843
6.00000
2.00000
12.64911
565.98009
5.65685
6.00000
4.00000
5.00000
2.00000
4.00000
4.00000
5.00000
17.83788

We think that quite all special cases are covered with this (except large numbers, but we both use long doubles and long long for integers).

Maybe someone got some more (tricky) test cases?

Thanks in advance,
Ildrial


[e] removed two cases (#nails = 0, but this is not asked of course)

[andmej]

I can't see why I am getting Wrong Answer. The output of my program for all the test cases in the board is exactly equal.

I'm using Andrew's Monotone Chain algorithm to find the Convex Hull of the points and then I repeatedly add the Euclidean distance between each pair of points to find the perimeter. If the perimeter is less than the initial rubber band length or there's only one nail, I output the initial rubber band length. If not, I output the perimeter. Here's my code with a detailed explanation:

Code: Select all

Code removed after acceptance.

This is the structure I will use to store the coordinates of each nail. Notice the variables are long long. I've also override the < operator, for sorting the points in lexicographical order.

Code: Select all

Code removed after acceptance.

This function is used in the Monotone Chain Convex Hull algorithm.

Code: Select all

Code removed after acceptance.

Next comes the function that actually finds a vector which contains all the points in the convex hull. If three points are co-lineal, the three points are reported in the convex hull.

Code: Select all

Code removed after acceptance.

The main function. It is appropriately commented.

Code: Select all

Code removed after acceptance.

This problem is driving me crazy. Please help me! I hope my code is clear enough. Any doubt, just ask!

In case you want to download it for testing it, here's the full link to my source code: Link removed after acceptance.

[mf]

return (x < p.x || (x == p.x && p.y));

That should be x < p.x || (x == p.x && y < p.y).

while (k >= 2 && cross(H[k-2], H[k-1], P) < 0) k--;
...
while (k >= t && cross(H[k-2], H[k-1], P) < 0) k--;

You should use <= there.

If three points are co-lineal, the three points are reported in the convex hull.

No. It would take more than just changing <= to < to get that code to report all collinear points, I think.
And you don't need them in this problem, anyway.

[andmej]

return (x < p.x || (x == p.x && p.y));

That should be x < p.x || (x == p.x && y < p.y).

while (k >= 2 && cross(H[k-2], H[k-1], P) < 0) k--;
...
while (k >= t && cross(H[k-2], H[k-1], P) < 0) k--;

You should use <= there.

Wow! That did the trick. You are really a guru, mf. Thanks a lot! Now I have a beautiful Accepted:

If three points are co-lineal, the three points are reported in the convex hull.

No. It would take more than just changing <= to < to get that code to report all collinear points, I think.
And you don't need them in this problem, anyway.

I can't see why changing <= to < is not enough for reporting collinear points in the convex hull. Mind explaining a little further?

Thanks again!

Edit: I submitted the same code with the < instead of <= and still got accepted. So the problem here only was the lexicographical ordering function.

[mf]

It can fail to work correctly if some point is repeated several times in the input.
E.g. try it on {(0,0), (0,1), (0,2), (1,0), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)}.

[andmej]

You are right. If I calculate the convex hull of those points with the < it gives a crazy answer, having more points than the original set. Thanks for the explanation, mf .

[Yulangie]

Hey guys

I spent so much time on this problem,
but still can't figure out my error.
For the cases posted above, i get the same results

Please can anyone post some i/o cases?

I use graham scan for my algorithm, and output the initial length of the ribbon if it is longer than the calculated
perimeter of the the convex hull, otherwise the calculated perimeter.
i also use long doubles, long long ints.
Is there anything I should pay attention to?

Thank you for help in advance

[Yulangie]

I finally figured it out.
Here are some input/output cases:

INPUT

10
4 9
0 0
1 1
-1 -2
2 1
2 3
1 -1
0 -2
-1 -3
-1 -1


2 9
0 0
100 100
200 0
100 -100
20 1
34 5
50 9
55 -8
101 100

5 6
0 0
0 0
0 1
0 2
1 0
2 0

1 7
8 0
8 3
10 0
10 1
10 2
12 3
12 0

2147483647 3
2147483647 0
-2147483647 0
-234 -234

2147483647 4
2147483647 0
-2147483647 0
-234 -23653464
235493 98734523

2134 4
192839 129438
-214214 2341
-1242141 -214583
987899 -83276

2 4
-34000 34000
34000 34000
-34000 -34000
34000 -34000

0 2
-2 -2
0 0

20 1
-2 -2

OUTPUT

14.06450
565.98009
6.82843
14.00000
8589934588.00003
8594732216.71442
4532567.45176
272000.00000
5.65685
20.00000

[krnara]

i take wrong anser 10hours!!!!!!!!!!!

somebody help me

i don't know what's wrong...


my abs algorithm

Code: Select all

int abs(int a)
{
	return a>=0?a:-1*a;
}

my dist algorithm

Code: Select all

double dist(Axis a,Axis b)
{
	double x = pow(a.x - b.x , (double) 2);
	double y = pow(a.y - b.y , (double) 2);

	return pow(x+y,(double)0.5);

}

my ccw algorithm

Code: Select all

int ccw(int x1,int y1, int x2, int y2,int x3 , int y3)
{
return  (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1) ;
}

my angle algorithm

Code: Select all

double Angle(int x1,int y1, int x2, int y2)
{
	if(x1 == x2)
	{
		if(y2>=y1)
		{
			return 90;
		}
		else
		{
			return 270;
		}
	}

	int dy = y2 - y1;
	int dx = x2 - x1;
	double ang ;
	ang  = (double)atan((double)dy /(double) dx ) / PI * (Circle / 2 );

	if( x2 -x1 < 0 )
	{
		ang += 180;
	}
	if( y2 - y1 <0)
	{
		ang += 360;
	}
	

	return ang;

}

my sorting algorithm

Code: Select all

void sorting(int N)
{
	Axis temp;
	
	
		for(int j = 1 ; j<N ; j++)
		{
			for(int k = j + 1; k<N ; k++)
			
				if(Angle(axis[0].x,axis[0].y,axis[j].x,axis[j].y ) > Angle(axis[0].x,axis[0].y,axis[k].x,axis[k].y ) )
				{
					temp.x = axis[j].x;
					axis[j].x = axis[k].x;
					axis[k].x = temp.x;

					temp.y = axis[j].y;
					axis[j].y = axis[k].y;
					axis[k].y = temp.y;


				}

				else if(Angle(axis[0].x,axis[0].y,axis[j].x,axis[j].y ) == Angle(axis[0].x,axis[0].y,axis[k].x,axis[k].y )  )
				{
					

					if(dist(axis[0],axis[j] ) < dist(axis[0],axis[k]) )
					{
						temp = axis[j];
						axis[j] = axis[k];
						axis[k] = temp;

					}


				}
			}

		
}

my main

Code: Select all

int main()
{
	
	int cnt;
	int ci;

	cin>>cnt;
	bool blank = false;

	while(cnt)
	{
		
		
		Axis print[120];
		int convex_hull[120];
		int ribbon;
		int nailNumber;
		int xt;
		int yt;
		int si = 0;
		int nt;
		int i = 0 , j = 0;
		

		cin>>ribbon>>nailNumber;
		
		nt = nailNumber;
		while(nt)
		{
			cin>>xt>>yt;
			axis[si].x = xt;
			axis[si].y = yt;
			si++;

			
			nt--;
		}

		if(blank == false)
		{
			blank  = true;
		}
		else
		{
			cout<<endl;
		}
		if(nailNumber == 1){float rib = ribbon;printf("%.5f\n",rib + 0);cnt--;continue;}


		//	cout<<"x"<<endl;
		axis[si].x = axis[1].x;
		axis[si].y = axis[1].y;


		int min = 0;
		ci = 1;
		
		for(i = 1; i<nailNumber ; i++)
		{
			if(axis[i].y < axis[min].y)
				min = i;
		}

		//cout<<min<<endl;

		int lowest = 0;

		for(j = 0 ; j<nailNumber; j++)
		{
			if(axis[j].y == axis[min].y)
				if(axis[j].x < axis[min].x)
				{
					lowest = j;
				

				}
		}



		int temp;

		temp = axis[lowest].x;
		axis[lowest].x = axis[0].x;
		axis[0].x = temp;
		
		temp  = axis[lowest].y;
		axis[lowest].y = axis[0].y;
		axis[0].y = temp;

			

			
		sorting(nailNumber);

	
		int stk[101];
		memset(stk,0,sizeof(stk));
		stk[0] = 0;
		stk[1] = 1;
		int ccnt = 2;

		int k = 0;
		
		stk[0] = 0;
		stk[1] = 1;

		for(int d = 1; d<nailNumber ; d++)
		{
			cout<<Angle(axis[0].x,axis[0].y,axis[d].x,axis[d].y)<<endl;
		}
	
		
		for(i = 2 ; i < nailNumber ; i++)
		{	
			while(ccnt >= 2 && ccw(axis[stk[ccnt-2]].x,axis[stk[ccnt-2]].y,axis[stk[ccnt-1]].x,axis[stk[ccnt-1]].y,axis[i].x,axis[i].y) <= 0)
			{
				
				ccnt--;
			}

			stk[ccnt] = i;
			ccnt++;
	
		}
		

	

		long  double length = 0.0;

		for(int q = 0 ; q<=ccnt ; q++)
		{
			
			length += dist( axis[ stk[q] ] , axis[stk[q+1]] );
			
			
		}

		if(ribbon >length)
		{
			float rib = ribbon;
			printf("%.5f\n",rib);
		}
		else
		{
			printf("%.5f\n",length);
		}


		cnt--;
	}
return 0;


}

[mf]

What's the point in splitting your code in pieces and posting some of them with useless comments? I can't assemble your whole program and test it.

I'd suggest to avoid using floating-point numbers when computing convex hull in this problem. You're not using them properly anyway - ever heard of epsilons?

And also why do try to cast the answer to float type? - it's probably not precise enough here.

Code: Select all

for(int q = 0 ; q<=ccnt ; q++)
{
         
   length += dist( axis[ stk[q] ] , axis[stk[q+1]] );
...

This piece of code tries to access stk[ccnt] and stk[ccnt+1], which, I think, may contain garbage.

i take wrong anser 10hours!!!!!!!!!!!

Too bad... go solve some other problems! Real contests only last 5 hours, and it's a real bad strategy to waste more than 2 hours on a single problem.

[CSEDU_1323]

i got RTE. can anyone tell me whats the problem ?

Code: Select all

removed afted AC