2014
03-02

# Planet Alignment

The Astrologically Clairvoyant Manufacturers have always used the celestial skies to make more accurate forecasts. Most of their predictions are based on a Star-Planet-Satellite alignment. There are some scientific reasons for this, mostly tidal changes: the gravitational pull of these celestial bodies will pull the water towards them. The greatest tides occur when the Sun, Earth, and Moon are perfectly aligned.

Always willing to expand its share of the market, the ACM has decided to generalize its predicitions to other planetary systems. However, on those systems the celestial bodies move at different speeds than in ours, so the predictions which depend on the Star-Planet-Satellite alignment must be recalculated. Can you help them automate some of their computations?

For some stellar system, at some point of the future denoted as t = 0, the star, a planet and a moon of the planet will be aligned on the galactic x axis. The star will be at position (0, 0), the planet will be at position (p, 0), and its planet will be at position (m, 0). The planet moves around the star in a perfect circle, on the galactic xy plane, and completes a revolution in u Earth days. Similarly, the moon revolves around the planet in v Earth days, in a perfect circle and on the same galactic plane. In other words, at t = u the planet will be back at position (p, 0), and at t = v the moon will once again have the same y coordinate as the planet and will be on the same side of the planet as when t was zero.

When will the three celestial bodies be aligned again?

The first line of input will contain a non-negative integer n, which represent the number of test cases. For each test case, you will be given one line containing the non-zero integers u and v, all of which could be negative. The distance between the moon and the planet will be strictly smaller than distance between the planet and the star, and the revolution durations won’t cause the celestial bodies to be permanently aligned. A positive revolution duration indicates that a celestial body revolves counter-clockwise, and a negative revolution duration indicates clockwise motion.

The first line of input will contain a non-negative integer n, which represent the number of test cases. For each test case, you will be given one line containing the non-zero integers u and v, all of which could be negative. The distance between the moon and the planet will be strictly smaller than distance between the planet and the star, and the revolution durations won’t cause the celestial bodies to be permanently aligned. A positive revolution duration indicates that a celestial body revolves counter-clockwise, and a negative revolution duration indicates clockwise motion.

2
1 -1
2 1

0.250
1.000

Alignment of the Planets     Problem Solving Report

【问题描述】（简述）

平面上给出N（1<=N<=770）个点的坐标（坐标均为0..15000之间的整数），要求求出有多少组三个点在一条直线上，并打印每组点的序号（即第几个输入的）。

【输入】

【输出】

【输入样例】

8

0 0

0 4

1 2

2 4

4 3

4 5

5 1

6 5

【输出样例】

1

1 3 4

【题目来源】

USACO 2005 December Bronze

http://acm.pku.edu.cn/JudgeOnline/problem?id=3174

【解题思路】
首先来分析输入输出样例：

这八个点看起来是这样的（左下角为坐标原点）：

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

在一条直线上的三个点的序号：

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

type

aa=record

x:integer;

y:integer;

end;

bb=record

a:integer;

b:integer;

c:integer;

end;

var

i,j,n,k,m,sum:integer;

tan:array[1..1000,1..1000]of double;

a:array[1..1000]of aa;

pp:array[1..1000]of bb;

begin

for i:=1 to n do readln(a[i].x,a[i].y);

for i:=1 to n-1 do

for j:=i+1 to n do begin

if a[i].x=a[j].x then tan[i,j]:=20000

else tan[i,j]:=(a[i].y-a[j].y)/(a[i].x-a[j].x);

end;

m:=1; sum:=0;

for i:=1 to n-2 do

for j:=i+1 to n-1 do

for k:=j+1 to n do

if tan[i,j]=tan[j,k] then begin

inc(sum);

pp[m].a:=i;

pp[m].b:=j;

pp[m].c:=k;

inc(m);

end;

writeln(sum);

for i:=1 to sum do writeln(pp[i].a,’ ‘,pp[i].b,’ ‘,pp[i].c);

end.

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

2. #include <cstdio>

int main() {