1k_trash's blog

Problems with standard 2D convex hull
By 1k_trash, 11 years ago, translation, In English

Hi, guys!

Today I tried to learn Graham Scan algorithm, but failed :(

Can you help me to find a bug in this code, please? http://ideone.com/IXFfS9 Algorithm is simple, but I still can't understand, why I have WA4 in problem A here http://mirror.codeforces.com/gym/100173

Can't even to find a test that can crash my solution :(

Thanks a lot!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I dont get what do you do in cmp() exactly, but might be a mistake in line 54:

this might be true 

float deltaX1 = p1.x - P.x, deltaX2 = p2.x - P.x;

instead of 

float deltaX1 = p1.x - P.y, deltaX2 = p2.x - P.x;
→ Reply