Nguồn đề bài: http://vn.spoj.com/problems/BALLGMVN/
1. Đề bài BALLGMVN spoj
Trong một hội thi Ballgame, ban tổ chức chuẩn bị một bàn lớn. Trên mặt bàn có n bi xanh đánh số từ 1 đến n và n bi đỏ đánh số từ n + 1 đến 2n. Mỗi trận đấu, các vận động viên sẽ chơi luân phiên nhau. Đến lượt chơi của mình, Hùng cần tìm 3 bi mà vị trí của chúng là thằng hàng hanu và sao cho trong số đó có hai bi đỏ và 1 bi xanh (khi đó ăn được một bi đỏ), hoặc là có hai bi xanh và 1 bi đỏ (khi đó được ăn 1 bi xanh).
Yêu cầu
Cho biết tọa độ trên mặt phẳng tọa độ Đề-các của vị trí và màu của các bi hiện tại trên bàn, bạn hãy giúp Hùng chọn 3 bi để chơi.
Input
- Dòng đầu ghi số nguên dương n.
- Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên là hoành độ và tung độ trên mặt phẳng tọa độ Đề-các của vị trí đặt bi xanh với chỉ sô i.
- Dòng thứ i trong số n dòng cuối cùng ghi hai số nguyên là hoàng độ và tung độ trên mặt phẳng tọa độ Đề-các của vị trí đặt bi đỏ với chỉ số n + i.
- Hoàng độ và tung độ không vượt quá 10^6, vị trí các bi là đôi một phân biệt.
Giới hạn
- 30% số test có n <= 2;
- 30% số test khác có n <= 100.
- 40% số test còn lại có n <= 1000.
Output
Ghi ra 3 chỉ số của các viên bi mà Hùng cần chọn, nếu không thể chọn được 3 bi nào, ghi ra -1. Nếu có nhiều đáp án, ghi ra một đáp án bất kì.
Example
Input:
3
1 1
2 2
4 9
3 3
6 20
8 100
Output:
1 2 4
2. Hướng dẫn giải BALLGMVN spoj – VOI 2014
Với mỗi điểm[i] từ 1–>N:
- Xem điểm[i] là gốc tọa độ, nên dựng được xNew[j]=x[j]-x[i] và yNew[j]=y[j]-y[i] với 1<=j<=N.
- Sort 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.
ĐPT: O(N^2 log N)
Với cách trên các bạn sẽ gặp chút rắc rối ở viên bi màu. vậy các bạn có thể chọn i làm gốc tọa độ của 1 tập, còn tập kia chỉ cần chọn 2 điểm có tỉ số x/y như hướng dẫn ở trên bằng nhau là được. Như vậy, các bạn có thể chia thành 2 tập viên bị màu xanh và viên bi màu đỏ. và làm tương tự như cách ở trên 2 lần.
3. Code tham khảo BALLGMVN spoj – VOI 2014
const fi='';
nmax=3000;
type data=longint;
var
f:text;
idd,xd,yd,idx,xx,yx,idnew:array[0..nmax+1] of data;
xynew:array[0..nmax+1] of real;
n:data;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
begin
readln(f,xx[i],yx[i]);
idx[i]:=i;
end;
for i:=1 to n do
begin
readln(f,xd[i],yd[i]);
idd[i]:=n+i;
end;
close(f);
end;
procedure Swap(var a,b:data);
var z:data;
begin
z:=a;
a:=b;
b:=z;
end;
procedure sort(l,r: longint);
var
i,j: longint;
x,y:real;
begin
i:=l;
j:=r;
x:=xynew[(l+r) div 2];
repeat
while xynew[i]<x do inc(i);
while x<xynew[j] do dec(j);
if not(i>j) then
begin
y:=xynew[i];
xynew[i]:=xynew[j];
xynew[j]:=y;
swap(idnew[i],idnew[j]);
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
procedure xuli;
var i,j,u,v:data;
begin
// N vien bi xanh lam goc
for i:=1 to n do
begin
for j:=1 to n do
begin
u:=xx[i]-xd[j];
v:=yx[i]-yd[j];
idnew[j]:=idd[j];
if v=0 then
xynew[j]:=high(data)
else
xynew[j]:=u/v;
end;
sort(1,n);
for j:=1 to n-1 do
if xynew[j]=xynew[j+1] then
begin
writeln(idx[i],' ',idnew[j],' ',idnew[j+1]);
readln;
halt;
end;
end;
// N vien bi do lam goc
for i:=1 to n do
begin
for j:=1 to n do
begin
u:=xd[i]-xx[j];
v:=yd[i]-yx[j];
idnew[j]:=idx[j];
if v=0 then
xynew[j]:=high(data)
else
xynew[j]:=u/v;
end;
sort(1,n);
for j:=1 to n-1 do
if xynew[j]=xynew[j+1] then
begin
writeln(idd[i],' ',idnew[j],' ',idnew[j+1]);
readln;
halt;
end;
end;
writeln(-1);
end;
begin
docfile;
xuli;
end.
