-

Geometry

# Given two points p (x1, y1) and q (x2, y2), calculate the number of integral points lying on the line joining them.
Solution
1. If the edge formed by joining p and q is parallel   to the X-axis, then the number of integral points 
   between the vertices is : 
        abs( y2 - y1 ) - 1

2. Similarly if edge is parallel to the Y-axis, then 
   the number of integral points in between is :
    abs( x2 - x1 ) - 1

3. Else, we can find the integral points between the
   vertices using below formula:
     GCD(abs( x2 - x1 ) , abs( y2 - y1 )) - 1

Comments

Post a Comment

Popular posts from this blog

URI 2994 Solution

-
URI 2994 - How much earn a Doctor?  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 SELECT d . name , ROUND (t . salary, 1 ) FROM doctors as d INNER JOIN ( SELECT id_doctor, SUM( (hours * 150 ) + ((hours* 150.0 * w . bonus) / 100.0 ) ) AS salary FROM work_shifts AS w INNER JOIN attendances AS a ON w . id = a . id_work_shift GROUP BY id_doctor ) AS t ON t . id_doctor = d . id ORDER BY t . salary desc ;
Read more

URI 2996 Solution

-
 URI 2996 - Package Delivery 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 SELECT year , sender, receiver FROM packages AS p INNER JOIN ( SELECT id_package, name AS sender FROM packages INNER JOIN users ON id_user_sender = id WHERE address <> 'Taiwan' ) AS sub1 ON sub1 . id_package = p . id_package INNER JOIN ( SELECT id_package, name AS receiver from packages INNER JOIN users ON id_user_receiver = id WHERE address <> 'Taiwan' ) AS sub2 ON sub2 . id_package = p . id_package WHERE color = 'blue' OR year = 2015 ORDER BY year DESC , sender DESC ;
Read more