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

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

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

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

»
11 лет назад, скрыть # |
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 .

»
11 лет назад, скрыть # |
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 )