Basketball tournament

0

0 votes
Hard, Algorithms, Approved
Problem

You are the manager of new basketball league. Your task is create schedule of games for this year.

League consists of n teams. Each team represents its home city. Each city i is placed at (xi,yi) and has population of pi.

Each pair of teams i and j (ij) has to play two games in any order: one of the games has to be played at home city of team i and the other one — at home city of team j.

You can choose any duration of the championship in days. Each day every team has to live in one of the given cities (this city is home city for some team). Plus each team can make at most one direct flight to another city every day.

For any team the cost of living at city i is Api per day.

For any team the cost of direct flight from city i to city j is B(xixj)2+(yiyj)2pipj.

Before the first day of the championship each team is located in its home city.

At the end of the championship each team can be located anywhere.

There is one more restriction, that difference between two consecutive games of a single team has to be at least k. For example, if k=1 then a team can play its games every day.

Your salary depends of the championship costs. So you want to minimize costs as much as possible. Find the best schedule you can.

Input format

The first line of input contains integers n and k (1n150, 1k5).

The second line of input contains integers A, B (1A,B103).

Then follow n lines. The i-th of them contains integers xi, yi and pi (0xi,yi105, 1pi105).

Output format

First line of output should contain integers l and q — the duration of championship, number of actions in championship.

l should be at most 109.

q should be at most 250000.

Then follow q lines.

The i-th of these lines contains integers d, t, a, b (1dl, 1t2, 1a,bn).

On t=1 action means that on day d team a took a flight to the city b.

On t=2 action means that on day d team a played with team b in the city where they were located on day d. Note that the city can be one of a or b.

Actions have to be printed in chronological order.

Scoring

Define your costs as C in certain test case. So you score for this test will be 105log(C).

Now test set contains 50 tests with n = 150. After contest we will add 50 tests more and rejudge all solutions.

Please, see comments below. They contains more informations about tests.

Time Limit: 4
Memory Limit: 512
Source Limit:
Explanation

Championship costs in the example are 9.5. So, the score will be 105log(9.5) = 225129.18.

Editor Image

?