SOLVE

LATER

House Travelling Problem

Problem

Editorial

Analytics

Bob is about to visit $$N$$ of his friends' houses. Each house is depicted as a point $$(x_i , y_i)$$ on the $$X-Y$$ plane. The length of roads between two houses $$i$$ and $$j$$ is defined as $$F(i, j) = (x_i - x_j)^2 + (y_i - y_j)^2$$.

There's a $$N \times N$$ matrix $$M$$ filled with 1s and 0s. $$M[i][j] = 1$$ denotes that it is possible to travel to $$i^{th}$$ House from $$j^{th}$$ House and vice versa. If $$M[i][j] = 0$$, it is not possible to travel to $$i^{th}$$ House from $$j^{th}$$ House and vice versa.

Now, Bob wants to visit all the houses, but the sum of length of all roads traveled should be maximum. There's one more restriction, he can use a maximum of $$(N - 1)$$ roads. Before starting the trip, he would like to know what is the maximum distance he can travel which satisfies all the given conditions. If it is not possible to visit all the houses, print out -1.

**Input Format:**

The first line contains $$N$$, the number of houses Bob wants to visit.

$$N$$ lines follow, each contains two space separated integers $$x_i$$ and $$y_i$$ which denotes the of the $$i^{th}$$ house on the $$X-Y$$ plane.

Again, $$N$$ lines follow, each contains $$N$$ space separated integers, each being 0 or 1, denoting the matrix $$M$$.

**Output Format:**

Print the required answer in one line.

**Input Constraints:**

$$1 \le N \le 3000 $$

$$-10^6 \le x_i, y_i \le 10^6$$

**Note:**

One road can be traversed any number of times , but its contribution would be taken only once. Also, there's large input data, please use faster i/o methods.

Explanation

This is the image for the given sample. Every house also has a road of length 0 to itself. We can use at max 2 roads which would be from (1,2) -> (8,8) -> (4,5). The total cost is 85 + 25 = 110.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic

Initializing Code Editor...

Challenge Name

Euromonitor International Hiring Challenge

Euromonitor International Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE

{"cd3af42": "/pagelets/problems-hint/algorithm/house-travelling-problem/", "7da6971": "/pagelets/show-submission/algorithm/house-travelling-problem/", "920ffcb": "/pagelets/recommended-problems/algorithm/house-travelling-problem/", "b5098c0": "/pagelets/problem-author-tester/algorithm/house-travelling-problem/", "77356d6": "/pagelets/suggested-problems/algorithm/house-travelling-problem/"}

realtime.hackerearth.com

80

95fd0c791b178c6071acf4e581981b8d8e2ad847

58a29e5cae2309f04b28

/realtime/pusher/auth/