# Sharing Inherited Land [closed]

You and your brother have inherited a rectanglar block of land. This block of land's corners are read in from stdio as TLX,TLY,TRX,TRY,BLX,BLY,BRX,BRY (all decimal numbers without units, T=Top, L=Left, B=Bottom, R=Right)

Unfortunately the city has seen fit to appropriate a small rectanglar section from inside your you newly aquired land. This appropriated land can be at any angle and in any position on your land. Its corners are read in from stdio as TLX,TLY,TRX,TRY,BLX,BLY,BRX,BRY (all decimal numbers without units).

You need to split this land evenly with your brother by building a fence. The fencing contractors can only build a single straight line fence. You need to supply them with the start and end co-ordinates which sit along the parameter of your property. These are written to stdio as SX,SY,EX,EY (all decimal numbers without units, S=Start, E=End)

The city has graciously agreed to allowed you to freely build the fence across their bit of appropriated property.

Provide a solution which can accept the 2 rectangle co-ordinates and return a correct solution which divides the property area equally for you and your brother.

visualized samples of potential input (white = your land, grey = city land):

{I'll insert the credit here after people have answered}

• Math analyse with several simple integrals for finding extremus. So sad, I don't remember details (It's just one way to solve, on paper) Jan 28, 2011 at 5:43
• Looks like here are mentioned several ways to solve en.wikipedia.org/wiki/Optimization_%28mathematics%29 Jan 28, 2011 at 18:00

C

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

enum mode
{
CORD_MODE_CONST = 1,
CORD_MODE_SLOPE = 2,
};
typedef struct point {
float x;
float y;
} CORD;

typedef struct l {
int mode;
float m;
float b;
}LINE;

typedef struct r {

CORD topL;
CORD botL;

CORD topR;
CORD botR;

CORD midRight;
CORD midBot;
CORD midLeft;
CORD midTop;

CORD center;
LINE vertLine;
LINE horLine;

} RECTANGLE;

void findBorderIntersection(RECTANGLE * pR, LINE * p);
int isPointContained(RECTANGLE * pR, CORD * pC1);
float dotProduct(float y1, float y2, float x1, float x2);
void findCenterOfRetangle(RECTANGLE * pR);
void findIntersection(LINE * pL1, LINE * pL2, CORD *pInt);
void findMidPointOfLine(CORD * pC1, CORD * pC2, CORD * pMid);
void getLine(CORD * pC1, CORD * pC2, LINE * pLine );

void dumpCord(char * pS, CORD * pC)
{
printf(" %s y:%f x:%f\n",pS,pC->y,pC->x);
}

int main()
{
RECTANGLE yourLand;
RECTANGLE cityLand;
LINE  lineThroughCenter;

memset(&yourLand,0x0, sizeof(RECTANGLE));
memset(&cityLand,0x0, sizeof(RECTANGLE));

scanf("%f%f%f%f%f%f%f%f",&(yourLand.topL.x),
&(yourLand.topL.y),
&(yourLand.topR.x),
&(yourLand.topR.y),
&(yourLand.botL.x),
&(yourLand.botL.y),
&(yourLand.botR.x),
&(yourLand.botR.y));

scanf("%f%f%f%f%f%f%f%f",&(cityLand.topL.x),
&(cityLand.topL.y),
&(cityLand.topR.x),
&(cityLand.topR.y),
&(cityLand.botL.x),
&(cityLand.botL.y),
&(cityLand.botR.x),
&(cityLand.botR.y));

/* Find center of your land */
findCenterOfRetangle(&yourLand);

/* Find center of city land */
findCenterOfRetangle(&cityLand);

/* Handle the case where the centers are right on top of each other */
if((yourLand.center.x == cityLand.center.x) &&
(yourLand.center.y == cityLand.center.y))
{
/* Find the line through center and the top border */
getLine(&(yourLand.midTop),&(cityLand.center),&lineThroughCenter);
}
else
{
/* Find the line through center of both lands */
getLine(&(yourLand.center),&(cityLand.center),&lineThroughCenter);
}

/* Find the border cords */
findBorderIntersection(&(yourLand),&lineThroughCenter);

return 0;
}
void findBorderIntersection(RECTANGLE * pR, LINE * p)
{
LINE line;
CORD c1;
CORD c2;

int bTop = 0;

getLine(&(pR->topL), &(pR->topR),&line);

/* Figure out if the the line goes through the top/bottom or right/left */
if( p->m != line.m)
{
findIntersection(p,&line, &c1);
bTop = isPointContained(pR,&c1);
}

if(bTop)
{
getLine(&(pR->botL), &(pR->botR),&line);
findIntersection(p,&line, &c2);
}
else
{
getLine(&(pR->topL), &(pR->botL),&line);
findIntersection(p,&line, &c1);

getLine(&(pR->topR), &(pR->botR),&line);
findIntersection(p,&line, &c2);
}

dumpCord("Border Cord1:",&c1);
dumpCord("Border Cord2:",&c2);

}

int isPointContained(RECTANGLE * pR, CORD * pC1)
{
float pointProduct1;
float vectorProduct1;
float pointProduct2;
float vectorProduct2;

vectorProduct1 = dotProduct((pR->topL.y - pR->botL.y),
(pR->topL.y - pR->botL.y),
(pR->topL.x - pR->botL.x),
(pR->topL.x - pR->botL.x));

pointProduct1 = dotProduct((pC1->y - pR->botL.y),
(pR->topL.y - pR->botL.y),
(pC1->x - pR->botL.x),
(pR->topL.x - pR->botL.x));

vectorProduct2 = dotProduct((pR->botR.y - pR->botL.y),
(pR->botR.y - pR->botL.y),
(pR->botR.x - pR->botL.x),
(pR->botR.x - pR->botL.x));

pointProduct2 = dotProduct((pC1->y - pR->botL.y),
(pR->botR.y - pR->botL.y),
(pC1->x - pR->botL.x),
(pR->botR.x - pR->botL.x));

if( (pointProduct1 <= vectorProduct1) &&
(pointProduct1 >= 0) &&
(pointProduct2 <= vectorProduct2) &&
(pointProduct2 >= 0))
{
return 1;
}

return 0;

}
float dotProduct(float y1, float y2, float x1, float x2)
{
return y1*y2 + x1*x2;
}

void findCenterOfRetangle(RECTANGLE * pR)
{
/* Find the mid point of the left side */
findMidPointOfLine(&(pR->topL), &(pR->botL), &(pR->midLeft));

/* Find the mid point of the right side */
findMidPointOfLine(&(pR->topR), &(pR->botR), &(pR->midRight));

/* Get the line */
getLine(&(pR->midLeft), &(pR->midRight), &(pR->horLine));

/* Find the mid point of the top side */
findMidPointOfLine(&(pR->topL), &(pR->topR), &(pR->midTop));

/* Find the mid point of the bottom side */
findMidPointOfLine(&(pR->botL), &(pR->botR), &(pR->midBot));

/* Get the line */
getLine(&(pR->midTop), &(pR->midBot), &(pR->vertLine));

/* Find the center of the first rectangle */
findIntersection(&(pR->horLine), &(pR->vertLine),&(pR->center));

}
void findIntersection(LINE * pL1, LINE * pL2, CORD *pInt)
{

if(pL1->mode == CORD_MODE_CONST)
{
pInt->x = pL1->m;
pInt->y = ((pL2->m * pInt->x) + pL2->b);
}
else if(pL2->mode == CORD_MODE_CONST)
{
pInt->x = pL2->m;
pInt->y = ((pL1->m * pInt->x) + pL1->b);
}
else
{
pInt->x = (pL2->b - pL1->b) / (pL1->m - pL2->m);
pInt->y = ((pL2->m * pInt->x) + pL2->b);
}
}

void findMidPointOfLine(CORD * pC1, CORD * pC2, CORD * pMid)
{
pMid->y = (pC1->y + pC2->y) / 2;
pMid->x = (pC2->x + pC1->x) / 2;
}
void getLine(CORD * pC1, CORD * pC2, LINE * pLine )
{

/* Find slope */
if((pC1->x - pC2->x) == 0)
{
pLine->mode = CORD_MODE_CONST;
pLine->m = pC1->x;
pLine->b = 0;
}
else
{
pLine->mode = CORD_MODE_SLOPE;
pLine->m = ((pC1->y - pC2->y) / (pC1->x - pC2->x));

/* Find y inter. */
pLine->b = pC1->y - (pLine->m * pC1->x);
}
}

• +1 Nice job. Especially with catching the same center edge case :) Jan 29, 2011 at 1:56
• Really neat, but seems you're missing bounds checks for the results, for example 0,0 6,0 0,4 6,4 with 2,0 3,0 2,1 3,1 gives a starting y of -7, outside of the land. Jan 29, 2011 at 2:18
• Yeah, I don't check for invalid data. I assume the order presented in the question is the only valid way to input data. Jan 29, 2011 at 2:32
• @Pemdas It's not invalid data, I've only formatted it like so to make it easier to read (for humans). Draw it out and take a look. Jan 29, 2011 at 2:38
• TLY is 0 BLY is 4...4 can not be below 0...well it can I suppose, but that is a limitation in my implementation. Jan 29, 2011 at 3:00

Assuming the land you inherit is square to the grid, this should do the job in Java.

import java.io.*;

class Land {

public static void main(String[] args) {

double[] corners = new double[16];
for(int i = 0; i < 16; i++) {
try {
} catch (Exception e) {
System.err.println("Error in input! Please try again.");
i--;
}
}

// Find mid point of own land
double lx = (corners[0] + corners[6])/2;
double ly = (corners[1] + corners[7])/2;
System.out.println("Mid point of your land: "+ lx + ", " + ly);

// Find mid point of city land
double cx = (corners[8] + corners[14])/2;
double cy = (corners[9] + corners[15])/2;
System.out.println("Mid point of city land: "+ cx + ", " + cy);

double sx, sy;

// Check for div by 0
if(cx-lx == 0) {
sx = lx;
sy = corners[1];
} else {
double m = (cy-ly)/(cx-lx);
// Find constant
double c = ly - (m * lx);
System.out.println("Constant: " + c);

if((m*corners[0] + c) >= corners[1]) {
sy = m*corners[0] + c;
sx = corners[0];
} else {
// use where line crosses x axis
sy = corners[1];
sx = (sy - c) / m;
}
}

// Apply the offsets to the lower corner
double ex = corners[6] - (sx - corners[0]);
double ey = corners[7] - (sy - corners[1]);

System.out.println("Fence start: "+ sx + ", " + sy);
System.out.println("Fence end  : "+ ex + ", " + ey);
}

}


Edit: just to clarify this also assumes a grid where top left is 0,0.

## Python 2.7

My thinking is:

• Line should pass through the centre of the brothers' land to split the 'additive area' equally.
• Line should pass through the centre of the city's land to split the 'subtractive area' equally.
• Line will pass through 'opposite edges' of the brothers' land.
• Whether this is on the left-right edges or top-bottom edges depends on in which 'diagonal quadrant' of the land the centre of the city's portion lies.

So:

• find centres
• find intersection points with edges

Code (Dense, huh? Only that pesky 'else' shorter than 70 chars! Not on purpose!):

cent = lambda p0,p1: {'x':(p0['x']+p1['x'])/2,'y':(p0['y']+p1['y'])/2}
dx = lambda p0,p1: p1['x']-p0['x']; dy = lambda p0,p1: p1['y']-p0['y']
dxdy=lambda p0,p1: 0 if (p0['x']==p1['x'] or p0['y']==p1['y']) else dx(p0,p1)/dy(p0,p1)
dydx=lambda p0,p1: 0 if (p0['x']==p1['x'] or p0['y']==p1['y']) else dy(p0,p1)/dx(p0,p1)
y_at_x = lambda p,lp0,lp1: lp0['y'] + (p['x']-lp0['x']) * dy(lp0,lp1)/dx(lp0,lp1)
print "input brothers' land TLX,TLY,TRX,TRY,BLX,BLY,BRX,BRY:"; land=input()
print 'input city land TLX,TLY,TRX,TRY,BLX,BLY,BRX,BRY:'; city=input()
land_cent = cent({'x':land[0],'y':land[1]},{'x':land[6],'y':land[07]})
city_cent = cent({'x':city[0],'y':city[1]},{'x':city[6],'y':city[7]})
in_half_tr = y_at_x(city_cent,{'x':land[0],'y':land[1]},{'x':land[6],'y':land[7]}) < city_cent['y']
in_half_br = y_at_x(city_cent,{'x':land[2],'y':land[3]},{'x':land[4],'y':land[5]}) < city_cent['y']
if in_half_tr ^ in_half_br # left or right = top-right XOR bottom-right
sp0 = {'x': land[0], 'y': land_cent['y'] - (land_cent['x']-land[0])*dydx(city_cent,land_cent)}
sp1 = {'x': land[2], 'y': land_cent['y'] - (land_cent['x']-land[2])*dydx(city_cent,land_cent)}
else:
sp0 = {'x': land_cent['x'] - (land_cent['y']-land[1])*dxdy(city_cent,land_cent), 'y': land[1]}
sp1 = {'x': land_cent['x'] - (land_cent['y']-land[5])*dxdy(city_cent,land_cent), 'y': land[5]}
print "splitting line from: (%s, %s) to (%s, %s)" % (sp0['x'], sp0['y'], sp1['x'], sp1['y'])


Seems to work for some test cases:

input brothers' land TLX,TLY,TRX,TRY,BLX,BLY,BRX,BRY:
0.0,0.0,4.0,0.0,0.0,4.0,4.0,4.0
input city land TLX,TLY,TRX,TRY,BLX,BLY,BRX,BRY:
1.0,0.0,3.0,0.0,1.0,1.0,3.0,1.0
splitting line from: (2.0, 0.0) to (2.0, 4.0)


And:

input brothers' land TLX,TLY,TRX,TRY,BLX,BLY,BRX,BRY:
0.0,0.0,4.0,0.0,0.0,4.0,4.0,4.0
input city land TLX,TLY,TRX,TRY,BLX,BLY,BRX,BRY:
0.0,0.0,1.0,0.0,0.0,1.0,1.0,1.0
splitting line from: (0.0, 0.0) to (4.0, 4.0)