Submit | All submissions | Best solutions | Back to list |
IITKWPCC - Count right angle triangles |
You are given n points in a 2D plane. You are asked these an inherently simple questions about them.
You have to find out number of right angle triangles (having base and height parallel to axis) with the property that length of base and height is same.
Input
First Line will n: number of points. (n <= 10^5).
For next n lines each line will contain two integers x and y. (-10^8 <= x, y <= 10^8).
Output
You have to output a single line containing the answer to question.
Example
Input:
5
0 0
1 0
2 0
0 1
0 2
Output:
2
Added by: | praveen123 |
Date: | 2013-08-05 |
Time limit: | 1s-6s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | IITK ACA CSE online judge |
hide comments
2024-02-19 12:42:46 Sushovan Sen
What is expected output for case 6 0 0 0 0 1 0 2 0 0 1 0 2 is it 2 or 4? |
|
2013-08-24 12:55:00 praveen123
@Miguel, Yes I have rejudged submissions with adding your test case |
|
2013-08-22 16:47:15 Miguel Oliveira
Did you rejudge all submissions already? It seems the cube cluster is indeed much faster than my computer. Didn't expect such a difference. |
|
2013-08-22 16:13:24 praveen123
@Miguel, I tested your test case in my machine, On my machine it was taking around 5 sec. With -O2 flag on, it took almost 1 sec. On spoj judge it took 1.72 sec. So I think that spoj judge machine is faster than ours :) . Thank you for the test case. Added to test files :) Last edit: 2013-08-22 16:14:01 |
|
2013-08-22 16:09:05 Miguel Oliveira
I sent you an e-mail with a test case where my solution needs 10s to compute the answer. Could you please check it? |
|
2013-08-22 16:09:05 praveen123
@Miguel For my code, worst time for any single test case is at most 1.18 sec. So it works for all the test cases with leaving around more than half of the time specified in the limit. Hence I think that time limit is perfectly justified. But if a lot of people think that time limit is too constrained, I will increase the time limit also. |
|
2013-08-22 16:09:05 Miguel Oliveira
are you sure your solution runs within 3s for all possible cases? my AC solution tries to take advantage of the dispersion of the points. This solution takes like 3x the time my other approach (which gets TLE) in cases where the points are more concentrated in a small range. edit: mixing both gave a huge speed up, but i'm still not convinced. This last AC code takes 7s on my computer (2.53ghz core2duo) in some cases. Last edit: 2013-08-21 23:41:06 |