brucewayne123's blog

need help in geometry problem
By brucewayne123, history, 8 years ago, In English

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

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

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

    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?

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

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply