
2006 South Central USA Regional Programming Contest 


Summary
Problem Set Results Doc Config Regional Welcome Rules Hints Compile Howto FAQ Sites ACU Baylor ECU LSU UTA PC^2 About PC^2 Documentation Local Mirror ACM Intl Prog Contest South Central US Regional Registration 
Introduction: When writing game programs, it is often useful to determine when two polygons intersect one another. This is especially useful in arcade games like Asteroids where one polygon could represent a spaceship while another represents a huge, unyielding chunk of space rock. Write a program that can determine which polygons of a given set intersect one another. Input: Input to this problem will begin with a line containing a single integer n indicating the number of datasets. Each data set consists of the following components:
Output: For each dataset in the input, output the heading "Data Set #z", where z is 1 for the first dataset, 2 for the second, etc. If this data set contained no intersecting polygons, output the message "no collisions" on its own line. Otherwise, output the list of all pairs of intersecting polygons, one pair per line, each pair formatted with the lowestnumbered polygon first. Output the polygon pairs in ascending order, sorting first by the lowestnumbered polygon in the set and then the second. Note: The definition of "intersecting" for the purpose of this problem means that two polygons either share an interior region (i.e., they overlap), or they share boundary points (i.e., they touch at a point or along an edge). Sample Input: 2 2 4 0,0 1,0 1,1 0,1 4 2,2 3,2 3,3 2,3 4 3 2,1 1,2 2,3 3 2,1 3,2 2,3 5 2,0 4,2 2,4 5,4 5,0 4 3,3 1,3 1,5 3,5 Sample Output: Data Set #1 no collisions Data Set #2 1 2 1 4 2 4 3 4

[Printable]
SCUSA Regionals 2006 2005 2004 2003 2002 2001 2000 