dharmang's blog

By dharmang, history, 9 years ago, In English

552D - Vanya and Triangles 11736806 I used Heron's formula to solve the problem but am getting wrong answer.. Is something wrong??

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

| Write comment?
»
9 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

You cannot compare floating point numbers , so easily .You need to use epsilon method . BTW , your logic is unnecessarily complicated . Let the three points be P1(x1,y1) , P2(x2,y2) and P3(x3,y3) . Now , the three points will not form a triangle only if they are collinear . To check that whether , they are collinear or not , we can make use of their slopes . Let m1 be the slope of P1 and P2 , and m2 be the slope of P2 and P3 . Now , m1 =(y2-y1)/(x2-x1) , and m2 =(y3-y2)/(x3-x2) . m1 = m2 => (y2-y1)*(x3-x2) = (y3-y2)*(x2-x1) ...(eqn. 1) (note this step , here we have tried to run away from floating point issues , they are always so messy) .

Now , we just have to count the triplets for which eqn. 1 is not satisfied . That is our answer .

Here , is my code that uses the same idea : http://mirror.codeforces.com/contest/552/submission/11731973 . We also , first sort the points , so that we do not miss some traingles .

»
9 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

If you want to calculate the area of a polygon ( here triangle as said in the problem statement ) using the coordinates of the given points,here's a good way to do this : Shoelace Formula.

But in this case as deer said you must use epsilon method . ( checking if area is zero or not )

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Awesome.. Just learnt a new formula.. Thanks man!! :) This formula works for all
    simple polygons righ??

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      The answer is "YES"

      You can use this formula for all of the polygons even the ones that are Concave as mentioned in the Wikipedia page related to this formula .