首页 > ACM题库 > HDU-杭电 > HDU 3112-Planet Alignment-线性结构-[解题报告]HOJ
2014
03-02

HDU 3112-Planet Alignment-线性结构-[解题报告]HOJ

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.
Sudoku

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

高鸣 2009年1月26日

【问题描述】(简述)

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

【输入】

第一行有一个正整数N,表示平面上有N个点。

接下来N行,买行包含两个非负整数,中间用一个空格隔开,分别表示一个点的横纵坐标。

【输出】

第一行有一个整数M,即有多少组三个点在一条直线上。

接下来M行,每行包含3个整数,每两个整数之间用一个空格隔开,表示每组的三个点的序号。

【输入样例】

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 . . . . . .  

  

  

这道题的本质就是搜索平面上能共线的三点,较好的方法是利用斜率(即直线的倾斜角α的正切值)。

首先是读入操作,因为这里要考虑到点的序号,因此我选择用记录类型来存每个点的坐标,而不是二维数组。

因为两点确定一条直线,所以我们可以求出每两个点的直线的斜率,并将其保存。这里我的方法是用二维数组,用点的序号作为位置,来填充该两点的直线斜率的值,就像这样:tan[x,y],x,y为两个点的序号。

另外要注意考虑到一个特殊情况,就是当两点横坐标相等时,该两点确定的直线斜率为无穷大,因此需要另外处理。我的方法是将这两个点的直线斜率直接赋值,当然,所赋的值不能是在数据规模下可能出现的斜率值(题目明确点的坐标不大于15000,这就意味着斜率的最大值(不算无穷大)为15000)。

接下来,由一个点出发,开二重循环,先确定第二的点,再去找第三个点。如找到了满足要求的解,则将这三个点的序号保存。这里我依然用记录类型,因为解可能有多个,用普通的数组不好办。

最后,输出解的个数,打印每组满足要求的三个点的序号。

  

  

  

  

下面是我的Pascal程序:

  

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

    readln(n);

    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.

参考:http://hi.baidu.com/hqohvakayfgjmur/item/2804fa3854a10c86b611db0b


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

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }