## 11096 - Nails

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Because the problem statements say..
what will be the final length of the rubber ribbon after surrounding the nails

AxM
New poster
Posts: 5
Joined: Thu Oct 19, 2006 5:21 pm
hahaha what a stupid mistake...

I need more I/O !

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
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
New poster
Posts: 1
Joined: Thu Dec 06, 2007 9:46 pm
Location: Switzerland
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)

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
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.

Last edited by andmej on Fri Jan 18, 2008 1:08 am, edited 3 times in total.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
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 .
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Yulangie
New poster
Posts: 3
Joined: Wed Dec 17, 2008 10:09 pm

### Re: 11096 - Nails

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
New poster
Posts: 3
Joined: Wed Dec 17, 2008 10:09 pm

### Re: 11096 - Nails

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
New poster
Posts: 2
Joined: Thu Jan 15, 2009 2:46 pm

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

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 11096 - Nails

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
New poster
Posts: 10
Joined: Mon Feb 25, 2008 8:22 pm