1994 USACO Competition Round Problems

Below are two problems that comprise the 1994  Competition Round of the 
USACO. Your job is to do as well as you can with one of the problems or 
both if you have the time. A good efficient solution to one of the 
problems should be your first goal. We have provided two problems so if 
you have no idea on how to attack one of them, you will still have a 
second chance. If you finish one and want to attempt another so much the 
better. However, it is better to have a complete solution to one problem 
than partial solutions to two problems. Of course, two perfect solutions 
is clearly the best but we do not expect that you will have the time to 
this. Also, Problem 1 is considered much harder than Problem 2 which 
will figure into our selection process. Good Luck!

Problem 1. CLOSED FENCES
A  CLOSED FENCE in the plane is a closed broken line with N corners and 
no intersections. The corners or vertices are listed in counter-
clockwise order in an array {xi yi}  i = 1,....N. Every pair of adjacent 
vertices defines a side of the fence. Thus {xi  yi   xi+1  yi+1 }is a 
side of the fence for i= 1,... N. Note that N+1=1 which connects the 
first and last vertices making the fence closed.

                         * x3 y3
                 x5 y5  / \
    x y *          *   /   \
                  / \ /     \
                 /   *       \
           x6 y6*   x4 y4     \
                |              \
                |               \
           x1 y1*----------------* x2 y2

Write a program which will do the following:

a) Test an array of vertices {xi yi },  i = 1,....N to see if the array 
is a valid fence. A valid fence is one that has no intersections. 

b) Suppose a person (with no height) is standing in the plane at 
position (x  y) and looks at the fence. What sides can the person see? 
The program must identify all sides of the fence that are visible or 
partially visible from (x y). This means there exists a ray from (x y) 
to the side which does not intersect any other side of the fence. A 
side that is parallel to the line of sight is not considered visible. 
In the figure above the segments  x3 y3  x4 y4  and  x5 y5 x6 y6 x1 y1 
consisting of two sides are visible or partially visible from x y. If 
only part of a side is visible, the entire side should be listed in 
the visible segment. Do not list just the visible portion.


Input file:  FENCE.DAT
Each data set in FENCE.DAT consists of:

a)  N (the number of corners in the fence, N<=30)
b) A sequence of corners consisting of two integers (each with absolute 
value <100) separated by a space and every two adjacent corners also 
separated by a space. The corners are given in counter-clockwise 
order. The sequence can continue on a new line if necessary.
c) A position x y  for the person observing the fence.
 
Output file:  FENCE.SOL file . 
The data set in FENCE.SOL consists of:

a) M (the number of visible sides).
b) A listing of each fence segment (one or more sides that are 
connected) with one segment per line.

 or

a) The message "NO FENCE" if the sequence given in the FENCE.DAT is not 
a valid fence.



 Different data sets will be separated by an empty record (that is, a 
line containing only the end of the line character. 



Sample Run
Input 
FENCE.DAT
4
0 0 2 0 1 1 0 1
2 2

4
0 0 2 0 1 1 1 -1
3 0

5
0 0 2 0 2 2 1 1 0 2 
4 3

13
0 0 7 0 5 2 7 5 5 7 3 5 4  9 1 8 2 5 0 9 -2 7 0 3 -3 1 
5 5

13
0 0 7 0 5 2 7 5 5 7 3 5 4 9 1 8 2 5 0 9 -2 7 0 3 -3 1
5 10

16
0 0 2 0 2 1 3 1 4 0 4 2 3 2 3 3 4 4 2 4 2 3 1 3 0 4 0 2 1 2 1 1
2 2

Output
FENCE.SOL
2
2 0 1 1 0 1

NO FENCE

2
2 0 2 2
1 1 0 2

7
-2 7 0 3 -3 1 0 0 7 0
5 2 7 5 5 7 3 5

5 
7 5 5 7 3 5 4 9 1 8
2 5 0 9

8
0 0 2 0
2 1 3 1
4 0 4 2
3 2 3  3
4 4 2 4
2 3 1 3
0 4 0 2
1 2 1 1





Problem 2.  ARITHMETIC PROGRESSIONS

 An arithmetic progression is of the form a, a+b, a+2b....., a+nb  where 
n=0,1,2,3...Assume a and b are non-negative integers (0,1,2,3,....).

Write a program  that finds all arithmetic progressions of length n in 
the set S of bisquares. The set of bisquares is defined as the set of 
all integers of the form p^2 + q^2 (where p and q are non-negative 
integers). As input, your program should accept the length of 
progressions N to search for and an upper bound M to limit the search to 
the bisquares in the range from 0 to M. Each line of the input file 
ARITH.DAT contains N M. Assume M <=10,000.

 
Sample Run

ARITH.DAT
 8 200
10 100

ARITH.SOL
Arithmetic progressions of length 8
taken from bisquares within the range
from 0 to 200:

Difference of 12:
1  13 25 37 49 61 73  85
13 25 37 49 61 73 85  97
25 37 49 61 73 85 97  109
37 49 61 73 85 97 109 121

Difference of 24:
1  25 49 73 97  121 145 169
2  26 50 74 98  122 146 170
25 49 73 97 121 145 169 193
26 50 74 98 122 146 170 194

There are 8 progressions.


Arithmetic progressions of length 10
taken from bisquares within the range
from 0 to 1000:

Difference of 12:
1  13 25 37 49 61 73 85 97  109
13 25 37 49 61 73 85 97 109 121

Difference of 24:
2   26  50  74  98  122 146 170 194 218
26  50  74  98  122 146 170 194 218 242
101 125 149 173 197 221 245 269 293 317
761 785 809 833 857 881 905 929 953 977

Difference of 36:
421 457 493 529 565 601 637 673 709 745

Difference of 48:
4   52  100 148 196 244 292 340 388 436
52  100 148 196 244 292 340 388 436 484
202 250 298 346 394 442 490 538 586 634

Difference of 60:
5  65  125 185 245 305 365 425 485 545
65 125 185 245 305 365 425 485 545 605

Difference of 72:
29 101 173 245 317 389 461 533 605 677

Difference of 84:
29  113 197 281 365 449 533 617 701 785
37  121 205 289 373 457 541 625 709 793
73  157 241 325 409 493 577 661 745 829
121 205 289 373 457 541 625 709 793 877
205 289 373 457 541 625 709 793 877 961

Difference of 96:
8   104 200 296 392 488 584 680 776 872
104 200 296 392 488 584 680 776 872 968

Difference of 108:
9 117 225 333 441 549 657 765 873 981

There are 21 progressions.