交汇的火力

发布于 2019-04-16  4 次阅读


题目描述

小D正在玩CS,喜欢思考的他看到无数子弹从他眼前飞过时想到了一个奇怪的问题:这么多子弹在空中飞来飞去,难道它们不会相撞吗?当然这是可能的.小D把两颗子弹轨迹相交的地方叫做”火力汇点”,显然如果让敌人站在火力汇点上那么他将受到更严重的伤害.小D想知道平面上的所有火力汇点以便对敌人造成更重的打击,但是小D数学很差,所以他找到了你,请你帮他计算出平面上所有火力汇点的坐标.小D用直线来描述子弹的轨迹,这种子弹很特别,它发射后会迸裂成两颗并沿相反方向飞行(汗!!那不是打自己),小D数学很差(已知),只会用直线的一般式表示每条直线y=kx+b.

输入

n
k1 b1
k2 b2
.
kn bn
第一行一个数n,表示直线数量
接下来n行,每行描述一条直线

2
1 0
-1 2

输出

一个数,火力汇点的个数
若交点不存在请输出No Fire Point. (结尾有小点哦)

1

思路

解方程然后进行判重,题目本来不难,但是有很多像精度问题的神奇问题(像我用C++就是写不出。。。)

var
  a,b:array[0..1000000] of longint;
  p:array[0..1000000,0..2] of real;
  i,j,k,n,m,l,r,ans,xx:longint;
  f:boolean;
  x,y,o:real;
begin
  assign(input,'firepoint.in'); reset(input);
  assign(output,'firepoint.out'); rewrite(output);
  readln(n);
  for i:=1 to n do
    readln(a[i],b[i]);
  for i:=1 to n do
    for j:=i+1 to n do
      begin
        if (a[i]=a[j]) then continue;
        l:=a[i]+a[j]*-1;
        if (a[i]=0) and (a[j]=0) then continue;
        r:=b[j]+b[i]*-1;
        if l=0 then x:=0 else
        x:=r/l;
        y:=a[i]*x+b[i];
        f:=false;
        for k:=1 to xx do
          if (p[k,1]=x) and (p[k,2]=y) then
            begin
              f:=true;
              break;
            end;
        if f then continue;
        inc(xx);
        p[xx][1]:=x;
        p[xx][2]:=y;
        inc(ans);
      end;
  if ans=0 then writeln('No Fire Point.')
    else writeln(ans);
  close(input);close(output);
end.
]]>