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

SD12

by Suresh Deoda

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 )

Comments
Please login or create a profile.
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