BALLGMVN – SPOJ

May 21, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/BALLGMVN/

Thuật toán:

Với mỗi điểm[i] từ 1–>N:

  • Dời gốc tọa độ về điểm[i] nên xNew[j]=x[j]-x[i] và yNew[j]=y[j]-y[i] với mỗi 1<=j<=N.
  • Sắp xếp các điểm theo giá trị x/y.
  • Các điểm có cùng giá trị chính là các điểm trên cùng một đường thẳng. Xử lý và in kết quả.

Độ phức tạp O(N^2 log N).

Code:

const   fi='';
        fo='';
        maxn=1000;
type    point=record
                x,y:longint;
                end;
var     i,j,n:longint;
        p:array[1..2*maxn] of point;
        tmp:longint;
        hold:array[1..2*maxn] of real;
        cs:array[1..2*maxn] of integer;
procedure mo;
begin
    assign(input,fi); reset(input);
    assign(output,fo); rewrite(output);
end;
procedure doc;
begin
    read(n);
    for i:=1 to 2*n do read(p[i].x,p[i].y);
end;
procedure QS(l,r:longint);
Var     i,j:longint;
        x,w:real;
        tg:longint;
Begin
x:=hold[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(hold[i]<x) do i:=i+1;
     While (x<hold[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=hold[i];hold[i]:=hold[j];hold[j]:=w;
          tg:=cs[i];cs[i]:=cs[j];cs[j]:=tg;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure xuly;
var     a,b,k:longint;
begin
    for i:=1 to n do
    begin
        for j:=n+1 to 2*n do
                begin
                    a:=p[j].x-p[i].x;
                    b:=p[j].y-p[i].y;
                    if b=0 then hold[j]:=low(longint)
                        else hold[j]:=a/b;
                end;
        for j:=n+1 to 2*n do cs[j]:=j;
        qs(n+1,2*n);
         for j:=n+2 to 2*n do
                if hold[j]=hold[j-1] then
                        begin
                            write(i,' ');
                            for k:=j-1 to j do write(cs[k],' ');
                            halt;
                        end;
    end;
    for i:=n+1 to 2*n do
    begin
        for j:=1 to n do
                begin
                    a:=p[j].x-p[i].x;
                    b:=p[j].y-p[i].y;
                    if b=0 then hold[j]:=low(longint)
                        else hold[j]:=a/b;
                end;
        for j:=1 to n do cs[j]:=j;
        qs(1,n);
         for j:=2 to n do
                if hold[j]=hold[j-1] then
                begin
                    write(i,' ');
                    for k:=j-1 to j do write(cs[k],' ');
                    halt;
                end;
    end;
    writeln(-1);
    halt;
end;
begin
    mo;
    doc;
    xuly;
end.
Chủ đề: SPOJ

Speak Your Mind

*