Блог пользователя dharmang

Автор dharmang, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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 .