BALLGMVN – SPOJ

Đề 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]j;
 If l