2012-11-07 16:00:00 UTC

# SD12

Status: Passed
Results: 275931 (cyc: 25, node: 1115)
CPU Time: 98.92
Score: 305272.0
Submitted at: 2012-11-02 15:31:44 UTC
Scored at: 2012-11-02 15:40:13 UTC

Current Rank: 1723rd (Highest: 127th )

Code
```function xyOut = solver(A, XY, wts)

A = triu(A,1);

% Find xy coordinates for first and second point on each line
[p1i,p2i] = find(A);

[~,sortedWts] = sort(wts(p1i));

p1i = p1i(sortedWts);
p2i = p2i(sortedWts);

nLines = length(p1i);

% Sort the pts based on weights
t = [p1i,p2i];
g = (wts(t(:,1)) > wts(t(:,2)));
t(g,:) = fliplr(t(g,:));
p1i =t(:,1); p2i =t(:,2);

p1 = XY(p1i,:);
p2 = XY(p2i,:);
nPoints = size(XY,1);

for i = 1:nLines-1
line1 = [p1(i,:) p2(i,:)];     %[x1 y1 x2 y2]

XY1  = XY;
for j = i+1:nLines
line2 = [p1(j,:) p2(j,:)]; %[x1 y1 x2 y2]

if areIntersecting1(line1,line2)

[linet1 shiftFlag] = lineShift(line1,line2);
if(shiftFlag == 1)
XY1(p1i(i),:) = linet1([1 2]);
else
[linet2 shiftFlag] = lineShift(line2,line1);
if(shiftFlag == 1)
XY1(p1i(j),:) = linet2([1 2]);
end
end

end

end

if(isequal(nPoints,size(unique(XY1,'rows'),1)))
XY  = XY1;
end

end

xyOut = XY;

end

function [line1 shiftFlag] = lineShift(line1,line2)
shiftFlag = 0;
if(((line2(1)-line1(1))*(line2(3)-line1(1)))<=0)
if(abs(line1(3) - (min(line2([1 3]))-1))<abs(line1(3) - (max(line2([1 3]))+1)))
line1(1)= min(line2([1 3]))-1;
shiftFlag = 1;
else
line1(1)= max(line2([1 3]))+1;
shiftFlag = 1;
end
elseif(((line2(2)-line1(2))*(line2(4)-line1(2)))<=0)
if(abs(line1(4) - (min(line2([2 4]))-1))<abs(line1(4) - (max(line2([2 4]))+1)))
line1(2)= min(line2([2 4]))-1;
shiftFlag = 1;
else
line1(2)= max(line2([2 4]))+1;
shiftFlag = 1;
end
end

if(shiftFlag == 1 && areIntersecting1(line1,line2))
shiftFlag = 0;
end

end

function bool = areIntersecting1(line1, line2)

x1 = line1(1);
y1 = line1(2);
x2 = line1(3);
y2 = line1(4);
x3 = line2(1);
y3 = line2(2);
x4 = line2(3);
y4 = line2(4);

% Test to see if the lines share exactly one endpoint. If so, the lines
% intersect if either of the free points lies on the line segment formed by
% the other two points.
if isequal([x1, y1], [x3, y3]) && ~isequal([x2, y2], [x4, y4])
bool = isPointOnSegment(x2, y2, x1, y1, x4, y4) || isPointOnSegment(x4, y4, x1, y1, x2, y2);
elseif isequal([x1, y1], [x4, y4]) && ~isequal([x2, y2], [x3, y3])
bool = isPointOnSegment(x2, y2, x1, y1, x3, y3) || isPointOnSegment(x3, y3, x1, y1, x2, y2);
elseif isequal([x2, y2], [x3, y3]) && ~isequal([x1, y1], [x4, y4])
bool = isPointOnSegment(x1, y1, x2, y2, x4, y4) || isPointOnSegment(x4, y4, x1, y1, x2, y2);
elseif isequal([x2, y2], [x4, y4]) && ~isequal([x1, y1], [x3, y3])
bool = isPointOnSegment(x1, y1, x2, y2, x3, y3) || isPointOnSegment(x3, y3, x1, y1, x2, y2);

% Next we check for parallel and coincident lines. Parallel lines
% obviously don't intersect. Coincident lines intersect if an endpoint from
% one of the lines lies on the other segment.
elseif ((y2 - y1)*(x4 - x3) == (x2 - x1)*(y4 - y3))%haveSameSlope(x1, y1, x2, y2, x3, y3, x4, y4)
if haveSameIntercept(x1, y1, x2, y2, x3, y3, x4, y4)  % lines are coincident

bool = (((x3-x1)*(x4-x1)<=0) && ((y3-y1)*(y4-y1)<=0)) || ...
(((x3-x2)*(x4-x2)<=0) && ((y3-y2)*(y4-y2)<=0)) || ...
(((x1-x3)*(x2-x3)<=0) && ((y1-y3)*(y2-y3)<=0)) || ...
(((x1-x4)*(x2-x4)<=0) && ((y1-y4)*(y2-y4)<=0));

else  % lines are parallel
bool = false;
end

% If we get this far, we're in the general case of two well-defined
% non-parallel lines. The lines formed by the two segments must intersect
% somewhere. Find this intersection point and determine if it lies on the
% segments.
else   % general case
% To avoid precision issues, represent point of intersection as a ratio
% of two integers: (Px, Py) = (Px_n/Px_d, Py_n/Py_d)
a1 = (x1*y2 - y1*x2);
b1 = (x3*y4 - y3*x4);

Px_n = a1*(x3 - x4) - (x1 - x2)*b1;
Px_d = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4);
Py_n = a1*(y3 - y4) - (y1 - y2)*b1;

Px_n = Px_n/Px_d;
Py_n = Py_n/Px_d;

bool = ((x1-Px_n)*(x2-Px_n)<=0) && ...
((y1-Py_n)*(y2-Py_n)<=0) && ...
((x3-Px_n)*(x4-Px_n)<=0) && ...
((y3-Py_n)*(y4-Py_n)<=0);

end

function bool = haveSameIntercept(x1, y1, x2, y2, x3, y3, x4, y4)
bool = (x4 - x3)*(y1*(x2 - x1) - x1*(y2 - y1)) == ...
(x2 - x1)*(y3*(x4 - x3) - x3*(y4 - y3));
end

function bool = isPointOnSegment(x1, y1, x2, y2, x3, y3)

bool =    ((y1 - y2)*(x3 - x1) == (x1 - x2)*(y3 - y1))&& ...
((x2-x1)*(x3-x1)<=0) && ...
((y2-y1)*(y3-y1)<=0);

end

end
```