Page 2 of 2
Posted: Fri Sep 28, 2007 7:11 pm
Because the problem statements say..
what will be the final length of the rubber ribbon after surrounding the nails

Posted: Sat Sep 29, 2007 1:11 am
hahaha what a stupid mistake...

I need more I/O !

Posted: Sun Oct 07, 2007 6:38 pm
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

Posted: Thu Dec 06, 2007 10:07 pm
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:
Input wrote: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
Output wrote: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?

Ildrial

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

Posted: Thu Jan 17, 2008 10:44 pm
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.
``````

Posted: Thu Jan 17, 2008 11:35 pm
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.

Posted: Fri Jan 18, 2008 1:01 am
mf wrote:
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.

Posted: Fri Jan 18, 2008 1:58 am
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)}.

Posted: Fri Jan 18, 2008 3:36 am
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 .

### Re: 11096 - Nails

Posted: Tue Dec 30, 2008 8:53 pm
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

### Re: 11096 - Nails

Posted: Sun Jan 04, 2009 11:47 pm
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

### somebody help mp!!!!!!!!!!!!!!!!!!!

Posted: Fri Jan 16, 2009 10:43 am
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;

}
``````

### Re: 11096 - Nails

Posted: Sat Jan 17, 2009 3:58 pm
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.

### Re: 11096 - Nails

Posted: Thu Oct 08, 2009 1:43 am
i got RTE. can anyone tell me whats the problem ?

Code: Select all

``````removed afted AC
``````