RO-TST 2005 Problem 14

On a $2004 \times 2004$ chess table there are 2004 queens such that no two are attacking each other\footnote[1]{two queens attack each other if they lie on the same row, column or direction parallel with on of the main diagonals of the table}.

Prove that there exist two queens such that in the rectangle in which the center of the squares on which the queens lie are two opposite corners, has a semiperimeter of 2004.