It_Wasnt_Me's blog

help in geometry problem
By It_Wasnt_Me, history, 4 years ago, In English

552D - Vanya and Triangles in this problem, shortly you should count all number of triangles with non-zero area.

My idea was to count all triangle I could which is NC3 then I will subtract zero-area triangles

zero-area triangle will occur if there is 3 points on the same line(horizontal, vertical) or have same diagonal.

Unfortunately I received (Wrong answer) and I can't prove why my solution is wrong, I tested it on several testcases and it gives Right answer.

https://ideone.com/iiuxuP Any help

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can try the following input:

3
-2 2
0 1
2 0

Your code prints 1, the correct answer is 0.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Edit: I was wrong, sorry. Yes the solution doesn't take care of all colinear points.

    → Reply