Answer to Question #155553 in C++ for Abu Ubayda

Question

Zahir is a young skating newbie, and he is learning to how to skate at the Chandrima Udyan each morning. As he is just learning the basics he can only move from one pathway to another by drifting north, east, south or west until he lands in another pathway. He has noticed that it’s impossible to get from some paths to some other by any sequence of moves if he follows that drifting rule. He now wants to go to some additional pathways, so that he can get from any pathway to any other one. He asked you to find the minimal number of pathways that need to be created. Assume all pathways to be at integer coordinates.

Input Format

The first line of input contains a single integer n (1 ≤ n ≤ 55) — the number of pathways. Each of the following n lines contains two integers xi and yi (1 ≤ xi, yi ≤ 1000) — the coordinates of the i-th pathway. Note that the north direction coinсides with the direction of y axis, so the east direction coinсides with the direction of the x axis. All pathway’s locations are distinct.

Constraints

n (1 ≤ n ≤ 55) (1 ≤ xi, yi ≤ 1000)

Output Format

Output the minimal number of pathways that need to be created in order for Zahir to be able to reach any pathway from any other one.

Sample Input 0

2
2 1
1 2

Sample Output 0

1

Sample Input 1

2
2 1
4 1

Sample Output 1

0

Answer 1

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int main()
{
int n;
scanf("%d",&n);

int dir[n][2];
for(int i=0;i<n;i++)
{
scanf("%d %d",&dir[i][0],&dir[i][1]);
}

//Now we need to input the location of Two-pathways(0 indexing based)
int p1,p2;
scanf("%d %d",&p1,&p2);

int i= p1;
int ans = 0;
while(i < p2)
{
int x = abs(dir[i][0] - dir[i+1][0]);
int y = abs(dir[i][1]-dir[i+1][1]);
ans += x>y?x:y;
i++;
}

printf("%d",ans);

return 0;
}