RIGHTRI - Editorial

editorial
, , , ,
1

Problem Link:

Practice
Contest

author: Tasnim Imran Sunny
tester: Roman Rubanenko
editorialist: Utkarsh Lath

Difficulty:

Easy

Pre-requisites:

High School Maths

Problem:

Given n triangles in cartesian plane, count the number of right triangles

Explanation:

Given a triangle, you have to tell if it is a right triangle. The author and tester used following property of right triangles.

C2 = A2 + B2

Where C is the length of longest side, A and B are length of other two sides.



int dist_square(point p, point q)
    return (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y)  
bool is_right_triangle(point p, point q, point r)
    c = dist_square(p, q)
    b = dist_square(p, r)
    a = dist_square(q, r)
    return  2*max(a, b, c) == a+b+c

The co-ordinates were kept very small so that there are no integer overflow errors.

Other Solution

Editorialist’s solution was based on the fact that dot product of two non zero vectors is zero iff they are orthogonal.



point operator-(point a, point b)
    return point(a.x-b.x, a.y-b.y)      
int dot(point p, point q)
    return p.x * q.x + p.y * q.y  
bool is_right_triangle(point p, point q, point r)
    point v1 = p-q
    point v2 = q-r
    point v3 = r-p
    return  dot(v1, v2) == 0 or dot(v1, v3) == 0 or dot(v2, v3) == 0

Solutions:

Setter’s solution
Tester’s Solution
Editorialist’s Solution

5 Likes
2

I think the test cases contain some cases where two points are same.

AS my sol http://www.codechef.com/viewsolution/2554621 got wa while
http://www.codechef.com/viewsolution/2554610 got AC.

3

This doesn’t look like m1*m2=-1 !?

2 Likes
4

Cases where (xi == xj), for some i!=j, are being counted twice. (missed an else before “if (x1==x2)” ?)

5

BUT THE ABOVE CONDITION IS WHEN ALL THREE ARE NOT EQUAL , SO BOTH
x1!=x2&&x2!=x3&&x3!=x1 and x1==x2 cann`t be true .

1 Like
6

@tijoforyou , sorry i submitted my ac solution earlier . Using the pythagorus theorem which i had to switch as m1*m2=-1 was not working.

7

I think, that triangle 0 0 0 2 1 1 is right, but your solution returns 0 - http://ideone.com/IrQv9X

5 Likes
8

@betlista Thanks . My bad changed a code little bit before submission caused me three wa . THANKS again.

9

i think pytha is the best suitable approach for this question////

10

could anyone fix my solution http://www.codechef.com/viewsolution/4332119 i think i am not missing anything :expressionless:

11

don’t use floats, floats yelds precision errors. you should use integer arithmetics to get precise results. So, to remove the floats, you should adapt the last comparisons so you don’t need to divide any variables.

so, for example, s1s2 == -1 would become (y2-y1)(y2-y3) == (x2-x1)*(x2-x3)

for more info on precision errors on using floats, see this:

12

#include<stdio.h>
int main()
{
int i, N, x1,x2,x3,y1,y2,y3,a,b,c, count=0;
scanf("%d",&N);
for(i=0; i<N; i++){
scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3);
if(x1!=x2 || x2!=x3 && y1!=y2 || y2!=y3 ){
a= (x1-x2)(x1-x2)+(y1-y2)(y1-y2);
b= (x2-x3)(x2-x3)+(y2-y3)(y2-y3);
c= (x3-x1)(x3-x1)+(y3-y1)(y3-y1);
if(a==b+c || b==c+a || c==a+b){
count++;
}
}}
printf("%d", count);
}