SPOJ.com - Problem IITKWPCC

IITKWPCC - Count right angle triangles

no tags

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

Submit solution!

hide comments



	Sushovan Sen: 2024-02-19 12:42:46 What is expected output for case 6 0 0 0 0 1 0 2 0 0 1 0 2 is it 2 or 4?
	praveen123: 2013-08-24 12:55:00 @Miguel, Yes I have rejudged submissions with adding your test case
	Miguel Oliveira: 2013-08-22 16:47:15 Did you rejudge all submissions already? It seems the cube cluster is indeed much faster than my computer. Didn't expect such a difference.
	praveen123: 2013-08-22 16:13:24 @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
	Miguel Oliveira: 2013-08-22 16:09:05 I sent you an e-mail with a test case where my solution needs 10s to compute the answer. Could you please check it?
	praveen123: 2013-08-22 16:09:05 @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.
	Miguel Oliveira: 2013-08-22 16:09:05 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

Submit solution!

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