Finish 2012-11-07 16:00:00 UTC

SD04

by Suresh Deoda

Status: Passed
Results: 347695 (cyc: 25, node: 960)
CPU Time: 25.813
Score: 349229.0
Submitted at: 2012-11-01 15:28:18 UTC
Scored at: 2012-11-01 20:53:28 UTC

Current Rank: 1758th (Highest: 71st )
Basis for: try 12 (diff)

Comments
Please login or create a profile.
Code
function xyOut = solver(A, XY, wts)


A = triu(A,1);




nNodes  = size(XY,1);

[~, SortedNds] = sort(wts);

for i = 1:ceil(0.66*nNodes)
    
    XYtest = XY;
    Pt2Shift  = XYtest(SortedNds(i),:);
    NdInd = SortedNds(i);
    
    shifts= 2*[ 1 1 -1 -1 ;1 -1  1 -1 ]';   
    Nsi = zeros(1,4);
    for si = 1:4
        XYtest(SortedNds(i),:) = Pt2Shift + shifts(si,:);
        Nsi(si) = numKnots2(XYtest,A,NdInd);
    end
    [~,ind1] = min(Nsi);
    shifts = shifts(ind1,:);
    for si = 1:2
        XYtest(SortedNds(i),:) = Pt2Shift + si*shifts;
        Nsi(si) = numKnots2(XYtest,A,NdInd);
    end
    [~,ind1] = min(Nsi(1:2));
     XYtest(SortedNds(i),:) = Pt2Shift + ind1*shifts;
         
    if(isequal(nNodes,size(unique(XYtest,'rows'),1)))              
              XY  = XYtest;
    end
    
end


xyOut = XY;

end



function [N] = numKnots2(XY,A,NdInd)

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

ind1 = find(p1i == NdInd);
ind2 = find(p2i == NdInd);

LinesToCheck = unique([ind1;ind2]);
% Check each pair of lines for an intersection
N = 0;
for i1 = 1:length(LinesToCheck)-1
     i = LinesToCheck(i1);
    line1 = [p1(i,:) p2(i,:)];     %[x1 y1 x2 y2]

    for j1 = i1+1:length(LinesToCheck)
        j = LinesToCheck(j1);
        line2 = [p1(j,:) p2(j,:)]; %[x1 y1 x2 y2]
        
        if areIntersecting1(line1,line2)           
            N = N + 1;
        end
        
    end
end
end


function bool = areIntersecting1(line1, line2)
% Determine if two line segments intersect.
%
% line1 = [x1, y1, x2, y2]
% line2 = [x3, y3, x4, y4]
%
% This function is robust to floating point precision issues assuming all
% input coordinates are integer-valued. If all coordinates have absolute
% values that do not exceed x, then the arithmetic operations used in this
% function could, as an intermediate step, produce a value with magnitude
% as large as 8*x^4. For double-precision floating point, this implies
% that the following must be satisfied:
%
% 8*x^4 < 2^53
%
% or equivalently, x < 5792.
%
% http://en.wikipedia.org/wiki/Line-line_intersection

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 haveSameSlope(x1, y1, x2, y2, x3, y3, x4, y4)
    if haveSameIntercept(x1, y1, x2, y2, x3, y3, x4, y4)  % lines are coincident
        bool = (isPointBetween(x3, x4, x1, 1) && isPointBetween(y3, y4, y1, 1)) || ...
            (isPointBetween(x3, x4, x2, 1) && isPointBetween(y3, y4, y2, 1)) || ...
            (isPointBetween(x1, x2, x3, 1) && isPointBetween(y1, y2, y3, 1)) || ...
            (isPointBetween(x1, x2, x4, 1) && isPointBetween(y1, y2, y4, 1));
    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)
    Px_n = (x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4);
    Px_d = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4);
    
    Py_n = (x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4);
    Py_d = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4);
    
    bool = isPointBetween(x1, x2, Px_n, Px_d) && ...
        isPointBetween(y1, y2, Py_n, Py_d) && ...
        isPointBetween(x3, x4, Px_n, Px_d) && ...
        isPointBetween(y3, y4, Py_n, Py_d);
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 = haveSameSlope(x1, y1, x2, y2, x3, y3, x4, y4)
bool = (y2 - y1)*(x4 - x3) == (x2 - x1)*(y4 - y3);
end

function bool = isPointOnSegment(x1, y1, x2, y2, x3, y3)
% Determine if point (x1, y1) is on the segment formed by (x2, y2) and (x3, y3).
bool = haveSameSlope(x2, y2, x1, y1, x1, y1, x3, y3) && ...
    isPointBetween(x2, x3, x1, 1) && ...
    isPointBetween(y2, y3, y1, 1);
end

function bool = isPointBetween(pt1, pt2, num, den)
% Determine if either of the following is satisfied:
% pt1 <= num/den <= pt2
% pt1 >= num/den >= pt2

bool = ((pt1*den <= num) && (num <= pt2*den)) || ...
    ((pt1*den >= num) && (num >= pt2*den));
end

end