[ACM] 计算直线的交点数

Question:

Problem Description

平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。

 

 

Input

输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量.

 

sub f{
 my ($m, $r, $s) = @_;
 my @f = @{$s};
 my @a;
 foreach(@f){
  my $n = ($m-$r)*$r + $_;
  push(@a, $n );
 }
 return @a;
}
my @init2 = (0,1);
my @init1 = (0);
my @init0 = (0);
my %tmphash;
$tmphash{2} = \@init2;
$tmphash{1} = \@init1;
$tmphash{0} = \@init0;
my $i = 3;
while(1){
 print "index is $i\n";
 my @t;
 for(my $r = 0; $r<$i; $r++){
  foreach(f($i, $r, $tmphash{$r})){

   push (@t, $_);
  }
 }
 @t = uniq(@t);
 $tmphash{$i} = \@t;
    for(@t){
  print "$_ ";
 }
    print "\ntrack $i finished\n";
 exit if( $i == 20);
 $i++;
}
sub uniq { return sort keys %{{ map { $_ => 4 } @_ }}; }