Q - Euclid in Manhattan（欧几里德距离==曼哈顿距离?）

Desciption

Consider a set of n points in a 2-D plane with integer coordinates. There are various ways of measuring distance between two points such as Euclidean , Manhattan , Chebyshev distance. These distances have important application , one of which is chess.

Consider that the ith point is located at (xi , yi). We want to find the number of pairs(i, j) such that the Euclidean distance between the points i and j is equal to the Manhattan distance between the same two points, i.e. Euclidean distance(i, j) = Manhattan distance(i, j).

√((xi − xj )^2 + (yi − yj )^2) - is called Euclidean distance

| xi − xj | + | yi − yj | - is called Manhattan distance

Note - All the n points given are considered different, even if they share the same coordinates.

Input

First line contains n, number of points in the plane Each of the following n lines contains two integers xi , yi

Output

Print the total number of such pairs.

Example

Input:

3

1 1

7 5

1 5

Output:

2

Input:

6

0 0

0 1

0 2

-1 1

0 1

1 1

Output:

11
解题思路：注意判断两个小数是否相等，一般采用作差法。如果两个小数的差值小于一个很小的精度，则视这两个小数相等。这题没给出n的范围，后台测试数据比较小，暴力O(n^2)水过。
AC代码：

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn=1e6+;

 int n,m=;double x[maxn],y[maxn];

 const double eps=1e-;

 double Eulc(double a1,double b1,double a2,double b2){

     return sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));

 }

 double Manh(double a1,double b1,double a2,double b2){

     return abs(a1-a2)+abs(b1-b2);

 }

 int main(){

     cin>>n;

     for(int i=;i<n;++i)cin>>x[i]>>y[i];

     for(int i=;i<n-;++i){

         for(int j=i+;j<n;++j){

             if(abs(Eulc(x[i],y[i],x[j],y[j])-Manh(x[i],y[i],x[j],y[j]))<eps)m++;

         }

     }

     cout<<m<<endl;

     return ;

 }

巴特西

Q - Euclid in Manhattan（欧几里德距离==曼哈顿距离?）

Desciption

Input

Output

Example

最新文章

热门文章