Graph Challenge

Problem code: GRAPHCH

All submissions for this problem are available.

Statement

You are given a modified graph with N vertices and M edges. Each vertex is a rectangle [ dimension of each vertex may be different ] . Your task is to place these vertices in 2-d space such that :

  • No two vertices overlap [ remember, they are rectangles ]
  • All rectangles have their sides parallel to the axis.
  • Rectangles cannot be rotated.

For every edge in the graph, add the manhattan distance between the centres of the vertex for each edge as the cost of a solution ( C ).
Now, there might be multiple ways to achieve this. So, you have to strive to keep C as low as possible.

Input

First line contains t ( ? 100 ) equal to the number of test cases. For each test case, the first line contains 2 space separated integers ( N and M respectively ). Then M lines follow, each line containing 2 integers x and y ( 0 ? x,y < N , x ? y ) denoting an edge between vertex x and y. Then follow N lines, where line number i contains 2 integers a and b denoting the dimension of the ith vertex [ Here, a denotes the length parallel to x-axis and b denotes the length parallel to y-axis ]

( Note : If the same pair x,y appears multiple times, it denotes multiple edges and hence, each pair contributes to the cost ).

NOTE : Please note that all solutions will be tested on another set of test data after the contest which will follow the same pattern for test case generation ( as mentioned in 'Test Case Generation' section ). The final score for a solution will be the score of solution on latter test data.

Output

For each test case, print N lines , each containing 2 floating point numbers X and Y, denoting the co-ordinates of the centre of vertex i.
Note : -109 ? X,Y ? 109 . Solutions not following the mentioned constraints will be adjudged as wrong answer.
Please note that the answers may not be optimal

Scoring

The Score for a solution = (C+1).
Your total score is the sum of your score for all the test cases.
You have to keep the score as low as possible.

Constraints

2 ? N ? 50
1 ? M ? 200 [ The edges are randomly generated ]
1 ? a,b ? 100000
There can be multiple edges between a pair of vertices.
Additionally for 50% of the cases 2 ? N ? 20. Also, for about 50% of cases, all vertices are squares [ a = b ] of same size.

Test Case Generation

There are about 100 cases in total. For first 50 cases, the number of vertex ( n ) is chosen as a random number in the interval [3,20]. The number of edges (m) is chosen as a random number in the range [2, n*(n-1)/2]. Then all edges are chosen as random pair of integers. All vertex are given the same dimension with the probability 0.5 else they are given a random dimension in [1,100000] * [1,100000].
For other 50 cases, n is chosen as a random integer in the interval [3,50]. m is chosen randomly from [2, min( n*(n-1)/2, 200) ]. Rest of the procedure remains the same.

Sample Input 


1
2 1
0 1
2 2
2 2

Sample Output 


2 2
10 3

Score for sample output : 10.0 ( Better answers may be possible )

Author: anshuman_singh
Date Added: 1-09-2010
Time Limit: 20 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

Which of our submissions will

thocevar @ 3 Nov 2010 12:40 AM

Which of our submissions will be used for final testing? All of them, highest scoring on preliminary tests or the latest?

I agree this needs to be

triplem @ 4 Nov 2010 08:49 AM

I agree this needs to be answered. I hope it is the latest submission only, as opposed to allowing all submissions, which has some pretty bad flaws.

Can the edges of the graph

tomas5 @ 5 Nov 2010 07:56 PM
Can the edges of the graph cross each other?

Hello Admin My question is

shadow @ 6 Nov 2010 06:06 PM

Hello Admin My question is same as Tomaz!!

Guess "by default" it means

Oleg @ 7 Nov 2010 05:16 PM

Guess "by default" it means all submissions will be rejudged.

Based on your feedback, we

admin @ 10 Nov 2010 01:21 AM

Based on your feedback, we are planning to rejudge the last submission for every user on new test data. Will update you guys more about the exact scoring rules by tomorrow. Thanks for your patience.

Maybe at least 10 last

Oleg @ 10 Nov 2010 12:58 PM

Maybe at least 10 last submissions ? Will be pity if test time will be 9.0 but on real data will be TL that will give 0 points.

@oleg: +1 @admin: can yu

suh_ash2008 @ 10 Nov 2010 07:49 PM

@oleg: +1

@admin: can yu please clarify the question posted by oleg before the contest ends.

We will judge only the last

admin @ 10 Nov 2010 11:47 PM

We will judge only the last accepted submission. We will extend the time limit on the new data to try and ensure that the accepted solution does not time out.

I had a clarification

Looterguf @ 11 Nov 2010 09:02 AM

I had a clarification question: if the bounding rectangles of the vertices touch along edges (not the edges of the problem, the edges of the rectangles), does it count as overlap?

@Gurtej: rectangles are

david_adm @ 11 Nov 2010 01:08 PM

@Gurtej: rectangles are allowed to touch.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions