BALLGMVN spoj – VOI 2014 – Trò Chơi Với Những Viên Bi
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 ...
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | 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. |
