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

need help in geometry problem
Автор brucewayne123, история, 8 лет назад, По-английски

problem link:- : http://mirror.codeforces.com/problemset/problem/552/D hello everyone! i am trying this problem on counting triangles with non zero area.. my approach is to represent a line segmnet between every 2 pair of points by the value (slope,constant) and using a map i am able to count how many points lie on this line segment reprsented by y=mx+c; for this i have used a set inside a map to avoid duplicacy and also for line segment with infinte slope i have used a seperate map.. after that i am simply subtracting the triangles from every line segment for total (NC3). i cant figure out the reason for wrong answer.. please help.. my submission:- http://mirror.codeforces.com/contest/552/submission/19069857

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by brucewayne123 (previous revision, new revision, compare).

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

This is a precision issue. Main advice: try to avoid doubles whenever you can.

Input is integer, so work with lines in form ax+by+c = 0. Also you can store only the number of times, that line was meeting, instead of set of points.

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

You can consider the representation y = mx+c . First, you can think about when two lines are parallel. That is when they have the same slope. So considering 3 points A,B,C, they form a triangle if there are not collinear if and only if the lines AB and BC don't have the same slope. So lets consider the two lines, for AB y=m1x+c1 and for BC y=m2x+c2 => m1 = (ya-yb)/(xa-xb) and m2 = (yb-yc)/(xb-xc). The slopes are basically equal when (ya-yb)*(xb-xc)=(xa-xb)*(yb-yc). You can do a brute force check every triangle and this will work. Note that you will still be working with integer numbers (so that's a plus). I hope this helps. You can check here my solution if you have doubts : http://mirror.codeforces.com/contest/552/submission/11648385

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    thanks a lot.. :) i understand the logic but i am having problem in understanding your code's complexity.. can you please explain how this complexity passed system tests?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      Given the contraints n<=2000, sometimes you can get accept even with an algorithm that is O(n^3) if your solution doesn't have a lot of instructions that are executed in the inner loop. Also the instructions are on integers and that makes the execution of the algorithm faster. That was the case of that solution. To give you an example, given the fact that you work with doubles your solution takes around 3.5 seconds, while mine took around 1.6s, this is due to the fact that when you make divisions and multiplications on doubles the instructions take more clock ticks to execute, while for a division or multiplication on integers takes one clock tick (I hope I am not mistaken on that one). You have to also keep in my mind that today's computers execute for 1ms around 10^7 clock ticks. So doing O(n^3) solutions is conceivable if you are careful to not have a lot of instructions in the inner loop and obviously that the instructions don't take a lot of clock ticks to execute.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Also if you still think on working with slopes. Because of the fact that the slope of a line AB is equal to (ya-yb)/(xa-xb) you can search to reduce this fraction by dividing each number to g = gcd(ya-yb,xa-xb) and you store the tuple (a,b,c) as (SkyFire stated above) in a map (a = (xa-xb)/g, b=(ya-yb)/g, c=?).. then you can do the same think as you did before. But you have to also pay attention if ya=yb or xa=xb. But I think it can be done nicely like that. This is a different view to the problem.

→ Ответить