2012-11-07 16:00:00 UTC

# Mercure1

by Chou Nay

Status: Passed
Results: 114268 (cyc: 20, node: 605)
CPU Time: 19.648
Score: 115288.0
Submitted at: 2012-11-01 17:11:03 UTC
Scored at: 2012-11-01 21:18:43 UTC

Current Rank: 1690th (Highest: 53rd )

Code
```function xyOut = solver(a, xyIn, wts)
global friendIndex

xy = xyIn;

%% General work on connectivity
nbSommet = length(wts);     % nb of points (int)
friendNb = sum(a);          % nb of friend (vect)
% friendIndex(k) is the vector (column) of friends of k (index)
friendIndex = cell(nbSommet);
for k=1:nbSommet
friendIndex{k} = find(a(:,k));
end

%% General work on cost function
score = numKnots(a, xyIn);
distanceSq = 0;

%% some ideas
%oneIndex = find(friendNb == 1);
%twoIndex = find(friendNb == 2);

%Trouver le nb d'intersections pour chaque sommet
%Prioriser les sommets par une fonction genre nbINter/weight
%Suivant cet ordre, essayer plusieurs strat?gies (dans un des 4 coins, ou au barycentre)

%% Solution
for n=1:10
for k = 1:nbSommet
bary = barycentre(xy, k);
newXY = round( (bary+xy(k, :))/2 );
if isPositionFree(xy, newXY)
xy(k,:) = newXY;
elseif isPositionFree(xy, round(bary))
xy(k,:) = round(bary);
end
end
end

xyOut = xy;

end

%% FUNCTIONS related to the current graph
function bool = isPositionFree(xy, pos)
% (verified)
% returns 1 if position is free, 0 otherwise
bool = 1;
xIndex = ( xy(:,1)==pos(1) );
bool = ~any(xy(xIndex,2)==pos(2));
end

function vect = getOrderIndex(xy)
vect = 1:size(xy,1);
end

function res = barycentre(xy, sommet)
global friendIndex
res = mean(xy(friendIndex{sommet}, :),1);
end

function res = closestPositions(pos)
res = zeros(9,2);
k=1;
for i=-1:1
for j=-1:1
res(k, :) = pos + [i, j];
k=k+1;
end
end
end

function res = closestFreePositions(pos)

end

%% GEOMETRIC FUNCTIONS

function N = numKnots(A, xy)
% Consider only unique lines (A is symmetric with ones on diagonal)
A = triu(A,1);
nLines = nnz(A);

% Find xy coordinates for first and second point on each line
[p1i,p2i] = find(A);
segments = [xy(p1i,:) , xy(p2i,:)];
N = 0;
for i = 1:nLines-1
seg1 = segments(i,:);     %[x1 y1 x2 y2]
for j = i:nLines
seg2 = segments(j,:); %[x3 y3 x4 y4]
N = N + nbIntersection(seg1, seg2);
end
end
end

function nb = nbIntersection(seg1, seg2)
% inspired from http://www.faqs.org/faqs/graphics/algorithms-faq/ (1.03)
% seg1 = [x1, y1, x2, y2]
% seg2 = [x3, y3, x4, y4]
Ax = seg1(1);
Ay = seg1(2);
Bx = seg1(3);
By = seg1(4);
Cx = seg2(1);
Cy = seg2(2);
Dx = seg2(3);
Dy = seg2(4);

rNom = (Ay-Cy)*(Dx-Cx) - (Ax-Cx)*(Dy-Cy);
sNom = (Ay-Cy)*(Bx-Ax) - (Ax-Cx)*(By-Ay);
rsDen = (Bx-Ax)*(Dy-Cy) - (By-Ay)*(Dx-Cx);

% they are not parallel
if rsDen ~= 0
% strict intersection
if rNom>0 && sNom>0 && rNom<rsDen && sNom<rsDen
nb = 1;
% one vertex is located on other edge
elseif rNom==0 || sNom==0 || rNom==rsDen || sNom==rsDen
nb = 2;
else
nb = 0;
end
% they are parallel
else
% they are colinear
if rNom == 0
% if not vertical
if Ax ~= Bx
if (Ax>min(Cx, Dx) && Ax<max(Cx, Dx)) || (Bx>min(Cx, Dx) && Bx<max(Cx, Dx))
nb = 2;
else
nb = 0;
end
% if vertical
else
if (Ay>min(Cy, Dy) && Ay<max(Cy, Dy)) || (By>min(Cy, Dy) && By<max(Cy, Dy))
nb = 2;
else
nb = 0;
end
end
% they are parallel but not colinear
else
nb = 0;
end
end
end
```