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

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=33&t=12153

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 !

I need more I/O !

Posted: **Sun Oct 07, 2007 6:38 pm**

Try This Case

Thanks

Keep posting

Sapnil

SUST

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
```

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:

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)

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

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).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

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)

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**:

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.
This function is used in the Monotone Chain Convex Hull algorithm.
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.
The main function. It is appropriately commented.
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.

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

Code: Select all

```
Code removed after acceptance.
```

Code: Select all

```
Code removed after acceptance.
```

Code: Select all

```
Code removed after acceptance.
```

Code: Select all

```
Code removed after acceptance.
```

Code: Select all

```
Code removed after acceptance.
```

In case you want to download it for testing it, here's the

Posted: **Thu Jan 17, 2008 11:35 pm**

That should be x < p.x || (x == p.x &&return (x < p.x || (x == p.x && 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:That should be x < p.x || (x == p.x &&return (x < p.x || (x == p.x && p.y));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,

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!

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)}.

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** .

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

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

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

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

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
my dist algorithm
my ccw algorithm
my angle algorithm
my sorting algorithm
my main

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;
}
```

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);
}
```

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) ;
}
```

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;
}
```

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;
}
}
}
}
```

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;
}
```

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.

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.

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

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

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.i take wrong anser 10hours!!!!!!!!!!!

Posted: **Thu Oct 08, 2009 1:43 am**

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

Code: Select all

```
removed afted AC
```