Electric Fence

This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

In this problem, ‘lattice points’ in the plane are points with integer coordinates.

In order to contain his cows, Farmer John constructs a triangular electric fence by stringing a ‘hot’ wire from the origin (0,0) to a lattice point (n,m), then to a lattice point on the positive x axis (p,0), with all between 1 and 32000, and then back to the origin (0,0).

A cow can be placed at each lattice point within the fence without touching the fence (very thin cows). Cows can not be placed on lattice points that the fence touches. How many cows can a given fence hold?

PROGRAM NAME: fence9

INPUT FORMAT

The single input line contains three space-separated integers that denote n, m, and p.

SAMPLE INPUT (file fence9.in)

7 5 10

OUTPUT FORMAT

A single line with a single integer that represents the number of cows the specified fence can hold.

SAMPLE OUTPUT (file fence9.out)

CODE

Java

C++

Pascal

ANALYSIS

Brian Jacokes

We can approach this problem in an easier manner if we flip the x and y axes, so we have a line from (0,0) to (M,N) and a line from (0,P) to (M,N). With this transformation, we see that if we draw a vertical line at any x position, it will intersect both of these line segments, so that we don’t have to worry about a special situation where it intersects one of the axes. Now we can cycle through all of the x-values, making sure to leave out the values at 0 and M (at 0 we will have one of the fence sides, which doesn’t count for holding cows, and at M we will have the two lines meeting at a point). At any x-value, the y-value of the along the segment from (0,0) to (M,N) is simply

rise / run * x

N / M * x

The y-value of the segment from (0,P) to (M,N) will be the initial y-value plus the rise over the run times x, or

P + (N-P) / M * x

Make sure you see how this will give us the y-value. Since each lattice point must be at an integer x-coordinate, all we have to do is add on the number of lattice points in between the two y-values at each x-value. The y-value along the segment (0,0) to (M,N) will always be lower than the y-value along the segment (0,P) to (M,N), so we will always subtract the first one from the second. Now all that is left is to find out the relationship between the y-values and the number of lattice points.

Now let us take the lower y-value and move it down until it is at the nearest lattice point that is at or below its current value, and let us take the higher y-value and move it up until it is at the nearest lattice point that is at or above its current value. If we don’t count the two endpoints, we still have exactly the same number of lattice points as before. It is now easy to see that the number of lattice points between the two values is

Y(bigger) - Y(smaller) - 1

If this is unclear, just try a few simple examples, such as 1 and 2, and see how it relates to larger y-values. The only step left is to move the y-values to the nearest lattice point that is above/below their current value.

Due to rounding errors, it is common that a number will be a very tiny fraction off the integer value, but it is still supposed to be an integer. Therefore, numbers must be checked to see how close they are to an integer value before they are rounded (if a y-value is already an integer, moving it up/down to the next y-value WILL change the number lattice points between the two points, which is exactly what we don’t want).

Therefore, when we round a number up, we first take its floor function (rounding it down). If the real y-value minus its floor is less than a very small number (say, 1e-6, for example), then we assume that this very small error is a result of rounding and leave the rounded up number as its floor. Otherwise, we increment the number by 1. In a similar manner we round numbers down.

#include <stdio.h>
#include <math.h>

int 
roundup (double a)
{
    int     b = int (floor (a));
    if ((a - b) > 1e-6)
	b++;
    return int (b);
}

int 
rounddown (double a)
{
    int     b = int (ceil (a));
    if ((b - a) > 1e-6)
	b--;
    return b;
}

int 
main ()
{
    FILE   *in = fopen ("fence9.in", "r");
    FILE   *out = fopen ("fence9.out", "w");
    int     a, N, M, P, interior = 0, temp;
    double  val1, val2, slope1, slope2;
    fscanf (in, "%d%d%d", &N, &M, &P);
    slope1 = double (N) / M;
    slope2 = double (N - P) / M;
    for (a = 1; a < M; a++) {
	val1 = slope1 * a;
	val2 = P + slope2 * a;
	temp = roundup (val2) - rounddown (val1) - 1;
	interior += temp;
    }
    fprintf (out, "%d\n", interior);
    return 0;
}

Alex Schwendner

Here is a O(ln N) solution

Pick’s Theorem states that if we have a polygon with lattice points as vertices, then:

A = I + B/2 - 1

where A is the area of the polygon, I is the number of lattice points inside of the polygon, and B is the number of lattice points on the boundary of the polygon. We are asked to find I. Thus, if we find A and B, w can use Pick’s Theorem to find I. The area is simply M * P / 2. We can find B by noting that the number of points that lie on a line with lattice endpoints (W,X) and (Y,Z) is 1 + gcd(|Y - W|, |Z - X|). We find the number of boundary points on each edge of the triangle, and subtract 3 (because we are double counting the vertices of the triangle) to find B. Once we have A and B, we can find I by using a rearrangement of Pick’s Theorem: I = A + 1 - B/2.

This solution is very fast, as it provides an explicit formula for I. The only step that is not constant-time is GCD(a,b), which is O(ln(max(a,b))) in the worst case.

#include <fstream.h>

inline int
gcd (int a, int b) {
    if (a < b){
	int t = a;
	a = b;
	b = t;
    }
    while (r = a % b) {
	a = b;
	b = r;
    }
    return (b);
}

int main () {
    int x, y, w;
    ifstream filein ("fence9.in");
    filein >> x >> y >> w;
    filein.close();

    if (y == 0) {
	ofstream fileout ("fence9.out");
	fileout << 0 << endl;
	fileout.close ();
	return(0);
    }

    // a = i + b/2 - 1
    // 2*a = 2*i + b - 2
    int a2 = y * w;
    int b = ((x > 0) ? gcd(x,y) : y) +
		((x == w) ? y : gcd(((x < w) ? (w - x) : (x - w)), y)) + w;
    int i = (a2 + 2 - b) / 2;
    ofstream fileout("fence9.out");
    fileout << i << endl;
    fileout.close();
    exit (0);
}