4
\$\begingroup\$

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):
Simple Sample

Skewed Sample

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

\$\endgroup\$

closed as off-topic by Timtech, Vereos, Hosch250, Justin, hildred Feb 18 '14 at 19:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Timtech, Vereos, Hosch250, Justin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ 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) \$\endgroup\$ – Nakilon Jan 28 '11 at 5:43
  • \$\begingroup\$ Looks like here are mentioned several ways to solve en.wikipedia.org/wiki/Optimization_%28mathematics%29 \$\endgroup\$ – Nakilon Jan 28 '11 at 18:00
  • 2
    \$\begingroup\$ Please add a winning criterion. \$\endgroup\$ – Timtech Feb 18 '14 at 14:48
3
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ +1 Nice job. Especially with catching the same center edge case :) \$\endgroup\$ – Dan McGrath Jan 29 '11 at 1:56
  • \$\begingroup\$ 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. \$\endgroup\$ – jtjacques Jan 29 '11 at 2:18
  • \$\begingroup\$ Yeah, I don't check for invalid data. I assume the order presented in the question is the only valid way to input data. \$\endgroup\$ – Pemdas Jan 29 '11 at 2:32
  • \$\begingroup\$ @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. \$\endgroup\$ – jtjacques Jan 29 '11 at 2:38
  • \$\begingroup\$ 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. \$\endgroup\$ – Pemdas Jan 29 '11 at 3:00
1
\$\begingroup\$

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) {

        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

        double[] corners = new double[16];
        for(int i = 0; i < 16; i++) {
            try {
                corners[i] = Double.parseDouble(r.readLine());
            } 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 {
            // Find gradient
            double m = (cy-ly)/(cx-lx);
            System.out.println("Gradient: " + m);
            // 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.

\$\endgroup\$
0
\$\begingroup\$

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 diagonal quadrant
  • 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)
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.