2013
11-12

# ‘Roid Rage

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 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:
1. A line containing a single positive integer m (1 <= m <= 10) indicating the number of polygons to analyze.
2. m lines, each representing a single polygon, with the first line describing polygon 1, the second line describing polygon 2, and so on. Each line begins with a single positive integer v (3 <= v <= 20) indicating the number of vertices describing this polygon. This is followed by v (x,y) coordinate pairs (0 <= x, y <= 100), each of which is a vertex of this polygon. The vertices are connected by edges in the order listed with the last vertex connected back to the first by a final edge. All polygons are "simple"; they do not self-intersect.

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 lowest-numbered polygon first. Output the polygon pairs in ascending order, sorting first by the lowest-numbered 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).

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

Data Set #1
no collisions
Data Set #2
1 2
1 4
2 4
3 4

/* @author: */
import java.util.*;
class point
{
int x,y;
point(){x=y=0;}
};

public class Main
{
static int cheng(point a,point b,point c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

static int dcheng(point a,point b,point c)
{
return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);
}

static int in(point []p,int n,point judge)
{
int c,j,k;point up,low,temp;
c=0;j=0;
while(p[j].y==judge.y)j++;
for(;j< n;j=k)
{
k=j+1;
while(p[k%n].y==judge.y&&p[k%n].x>judge.x) k++;
up=p[j];
low=p[k%n];
if(up.y< low.y){	temp=up;up=low;low=temp; }
if(up.y< judge.y||low.y>judge.y)continue;
if(cheng(low,up,judge)<=0&&k==j+1)continue;
c++;
}

return c%2;
}

static point p[][] = new point[30][];
static int len[] = new int[50];

static boolean judge( int a, int b ) {
point p1[] = p[a], p2[] = p[b];
int i, j;
for( i=0; i< len[a]; i++ )
for( j=0; j< len[b]; j++ ) {
if( cheng( p1[i], p2[j], p2[(j+1)%len[b]] ) == 0 &&
dcheng( p1[i], p2[j], p2[(j+1)%len[b]] ) <= 0 )
return true;
}

for( i=0; i< len[b]; i++ )
for( j=0; j< len[a]; j++ )
if( cheng( p2[i], p1[j], p1[(j+1)%len[a]] ) == 0 &&
dcheng( p2[i], p1[j], p1[(j+1)%len[a]] ) <= 0 )
return true;

for( i=0; i< len[a]; i++ )
if( in( p2, len[b], p1[i] ) > 0 )
return true;
for( i=0; i< len[b]; i++ )
if( in( p1, len[a], p2[i] ) > 0 )
return true;
return false;
}

public static void main(String args[]) throws Exception
{
int t, n, j, i, k=1, g;
int ans[] = new int[500];
int answer;
String w;

Scanner cin = new Scanner( System.in );
t = cin.nextInt();
while( t-- != 0 ) {
n = cin.nextInt();
for( i=0; i< n; i++ ) {
len[i] = cin.nextInt();
p[i] = new point[len[i]];
for( j=0; j< len[i]; j++ ) {
w = cin.next();
g = w.indexOf( ',' );
p[i][j] = new point();
p[i][j].x = Integer.parseInt( w.substring(0,g) );
p[i][j].y = Integer.parseInt( w.substring(g+1) );
}
}
answer = 0;
for( i=0; i< n; i++ )
for( j=i+1; j< n; j++ )
if( judge( i, j ) )
ans[ answer++ ] = (i+1)*100+j+1;
System.out.println( "Data Set #" + k );
k++;
if( answer == 0 )
System.out.println( "no collisions" );
else {
for( i=0; i< answer; i++ )
System.out.println( ans[i]/100 + " " + ans[i]%100 );
}

}
return;
}
}

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

2. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的