2013
11-12

# Alignment of the Planets

Actually, this problem is about alignment of N (1 <= N <= 770) cows numbered 1..N who are grazing in their field that is about 15,000x15,000 units. Their grazing locations all fall on integer coordinates in a standard x,y scheme (coordinates are in the range 0..15,000).

Bessie looks up and notices that she is exactly lined up with Sara and Julie. She wonders how many groups of three aligned cows exist within the field.

Given the locations of all the cows (no two cows occupy the same location), figure out all sets of three cows are exactly collinear. Keep track of the sets, sorting the cows in each set by their ID number, lowest first. Then sort the sets by the three ID numbers (lowest first), breaking ties by examining the second and third ID numbers.

Line 1: A single integer, N

Lines 2..N+1: Line i+1 describes cow i’s location with two space-separated integers that are her x and y coordinates

Line 1: A single integer that is the number of sets of three cows that are exactly collinear. A set of four collinear cows would, of course, result in four sets of three collinear cows.

Lines 2..?: Each line contains three space-separated integers that are the cow ID numbers of three collinear cows. The lines are sorted as specified above. This output section is empty if no collinear sets exist.

8
0 0
0 4
1 2
2 4
4 3
4 5
5 1
6 5

1
1 3 4

Be careful of floating point arithmetic. Floating point comparison for equality almost never works as well as one would hope.

Explanation of the sample:

Eight cows grazing on a grid whose lower left corner looks like this:

. . . . * . *
* . * . . . .
. . . . * . .
. * . . . . .
. . . . . * .
* . . . . . .

The digits mark the collinear cow IDs:

. . . . * . *
* . 4 . . . .
. . . . * . .
. 3 . . . . .
. . . . . * .
1 . . . . . .

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class point{
int x,y;
}

public class Main {
static final int N = 770+10;
static int n;
static point way[] = new point[N];
static void start(){
int i;
for(i=0;i< N;++i)
way[i] = new point();
}

public static void main(String[]args) throws Exception{

start();
int i,j,k,sum;
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
cin.nextToken();
n = (int) cin.nval;
for(i=0;i< n;++i){
cin.nextToken();
way[i].x = (int)cin.nval;
cin.nextToken();
way[i].y = (int)cin.nval;
}
sum = 0;
for(i=0;i< n;++i) for(j=i+1;j< n;++j) for(k=j+1;k< n;++k){

if((way[i].y-way[j].y)*(way[j].x-way[k].x)==(way[i].x-way[j].x)*(way[j].y-way[k].y)){
sum++;
out.println((i+1)+" "+(j+1)+" "+(k+1));
}
}
System.out.println(sum);
out.flush();

}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;

3. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？