INFOMAN брой 20
{ Входни данни :
2
0 0 1 1
0 3 1 4
0 0
XVII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА
Първи ден - Задача 3. Квадрати
В координатната равнина са дадени N (0<N<100) квадрата и
точка P. Разстояние между точка P и квадрат наричаме
дължината на най-късата отсечка, която съществува между
точката P и някоя от точките, принадлежащи на контура или
на вътрешността на квадрата. Ако точката P е вътрешна за
квадрата, тогава разстоянието й до квадрата приемаме за
нула. Възможно е, някои от дадените квадрата да са частично
или изцяло припокриващи се. Допуска се, някои от квадратите
да са изродени в точка, т.е. да имат съвпадащи върхове.
Напишете програма SQUARE.EXE, която сортира квадрати в
нарастващ ред спрямо разстоянията им до точката P.
Входните данни са дадени в текстов файл SQUARE.INP. В
първия ред на файла е записано цялото число N. Във всеки
от следващите N реда са дадени по 4 цели числа от диапазона
(Ц9999, 9999). Първите две от тези числа са x- и
y-координатата на един от върховете на поредния от дадените
квадрати, а втората двойка числа са x- и y-координатата на
срещуположния връх на същия квадрат. В последния ред на файла
са записани x- и y-координатата на точката P. За разделител
между числата, които са разположени на един ред във файла,
е използвана по една шпация.
Изходни данни трябва представляват редица от номерата на
квадратите така, както ги е подредила вашата програма.
Номерата на квадратите са дефинирани съгласно реда на
появяването им във входния файл. Ако два квадрата имат
равни разстояния до точката P, тогава номерата им трябва да
са изведени по нарастващ ред. Изходният текстов файл трябва
да има име SQUARE.OUT и числата в него трябва да са написани
на един ред и да са отделени с по една шпация.
РЕШЕНИЕ:
Решението е директно -
намират се разстоянията до квадратите и се сортират. Сортирането е лесно,проб-
лема е в намирането на разстоянията.
Нека върховете на квадрата, до който търсим разстоянието са A, B, C, D, нека
AB = a. Дадените върхове са A и D, за да намерим положението на B и C трябва
да пресметнем полярните координати на D с начало A (тоест след като трансли-
раме така че A = (0, 0)). Нека à е ъгловата част от полярните координати на D.
Тогава преобразуваме полярните координати (à+ã/2, a) и (à-ã/2, a) в декартови
и правим обратната транслация (O отива в A) точките (à+ã/2, a) и (à-ã/2, a)
след транслацията са върховете B и C.
Изчисляването на разстоянията се разделя на няколко случая :
1) ABCD съвпадат (квадрата е изроден).
2) P е в квадрата.
3) P е извън квадрата.
3.1) Правата P + tv (където v е вектор ортогонален за една от страните на
квадрата а t е параметър) пресича една от страните на квадрата във
вътрешна точка.
3.2) Няма такъв вектор v за който P + tv да пресича квадрата във вътрешна
точка.
1) и 2) се проверяват и се разглеждат като специални (тривиални) случаи.
3.1) Намира се пресечната точка като се решава система от уравнения.
!!! 3.1) Трябва да се приложи два пъти понеже има две страни, които P + tv
пресича във вътрешна точка и да се вземе разстоянието до тази точка,
която е най-близо. Векторите v,който се пробват са (A - B) и (C - D)
-- (A - B) е вектора в B , който сочи към A.
3.2) Избира се минималното разстояние от 4-те върха на квадрата.
В допълнение искам да спомена, че е може би по-лесно за реализация на 3.1 ако
се нормализира v и се пресметне |(Q - P) v| (където Q е връх от страната,
която P + tv пресича), което е точно нужното разстояние. Използвам по-сложния
начин за да мога да намеря пресечната точка и при визуализацията да проверя
дали програмата работи вярно.
Jivko Ganev
}
{сложете $ пред DEFINE за да стартирате програмата с визуализация}
{DEFINE DRAWGFX}
uses
graph;
const
infile = 'square.pas';
outfile = 'square.out';
eps = 1E-14;
bgipath = 'C:\BP70\BGI';
type
Tsq = record x1, y1, x2, y2, x3, y3, x4, y4 : extended; end;
Trec = record id : longint; dist : extended; end;
Tpoint = record x, y : extended; end;
var
SQ : array [1..110] of Tsq;
A : array [1..110] of Trec;
p : Tpoint;
n : longint;
scale : extended;
tx, ty, maxx, maxy : extended;
lastx, lasty : extended;
gd, gm : integer;
procedure indata;
var fin : text;
i : longint;
x1, y1, x2, y2 : extended;
begin
assign(fin, infile);
reset(fin);
readln(fin); {Това е заради това, че входа се чете от source фаила}
read(fin, n);
for i := 1 to n do
begin
read(fin, x1, y1, x2, y2);
SQ[i].x1 := x1;
SQ[i].y1 := y1;
SQ[i].x2 := x2;
SQ[i].y2 := y2;
end;
read(fin, p.x, p.y);
close(fin);
end;
procedure outdata;
var fout : text;
i : longint;
begin
assign(fout, outfile);
rewrite(fout);
for i := 1 to n do write(fout, A[i].id, ' ');
close(fout);
end;
{
насочено лице, cross product - както искате го наричаите:
връща 1 ако (x1, y1), (x2, y2), (x3, y3) са по часовниковата стрелка
-1 ако (x1, y1), (x2, y2), (x3, y3) са обратно на часовниковата стрелка
0 ако (x1, y1), (x2, y2), (x3, y3) са на една права
}
function cw(x1, y1, x2, y2, x3, y3 : extended) : longint;
var c : extended;
begin
c := x1 * (y3 - y2) +
x2 * (y1 - y3) +
x3 * (y2 - y1);
{c се сравнява директно,защото граничните случаи не влияят на вярноста на
програмата}
if c < 0 then cw := -1 else
if c > 0 then cw := +1 else cw := 0;
end;
{решава системата от уравнения
| x1 + k * ux = x2 + m * wx
| y1 + k * uy = y2 + m * wy
като (x1,y1) + ku = пресечната точка на (x1,y1) + ku и (x2,y2) + mw
връща в (resx,resy) координатите на пресечната точка}
procedure inter(x1, y1, x2, y2, ux, uy, wx, wy : extended;
var resx, resy : extended);
var k : extended;
begin
k := ( wy * (x2 - x1) + wx * (y1 - y2) ) /
(ux * wy - uy * wx);
resx := x1 + k * ux;
resy := y1 + k * uy;
end;
{надявам се това няма нужда от коментар :) }
function distance(x1, y1, x2, y2 : extended) : extended;
begin
distance := sqrt( sqr(x1 - x2) + sqr(y1 - y2) );
end;
{връща ъгловата част от полярните координати на (x,y)}
function theta(x, y : extended) : extended;
begin
if abs(x) < eps then
begin
{ Разглежда се като специален случай , защото x ~= 0 => (y / x) ~= inf }
if y > 0 then theta := pi / 2
else theta := - pi / 2;
end else
begin
{Понеже функцията arctan връща ъгъл в интервала (-ã,+ã) случая
x < 0 се разглежда специално, за C програмистите това не е нужно --
използваите atan2}
if x > 0 then theta := arctan(y / x)
else theta := arctan(y / x) + pi;
end;
end;
{връща разстоянието до квадрата s,
(lastx,lasty) е точката която е най-близо до P --
използва се при визуализацията }
function dist(s : Tsq) : extended;
var res : extended;
v1, v2, v3, v4 : Tpoint;
c13, c32, c24, c41 : longint;
ux14, uy14, ux13, uy13, wx, wy, intx, inty : extended;
begin
v1.x := s.x1; {A}
v1.y := s.y1;
v2.x := s.x2; {D}
v2.y := s.y2;
v3.x := s.x3; {C}
v3.y := s.y3;
v4.x := s.x4; {B}
v4.y := s.y4;
if (v1.x = v2.x) and (v1.y = v2.y) then
begin
{1)}
dist := distance(v1.x, v1.y, p.x, p.y);
lastx := v1.x;
lasty := v1.y;
exit;
end;
c13 := cw(v1.x, v1.y, v3.x, v3.y, p.x, p.y);
c32 := cw(v3.x, v3.y, v2.x, v2.y, p.x, p.y);
c24 := cw(v2.x, v2.y, v4.x, v4.y, p.x, p.y);
c41 := cw(v4.x, v4.y, v1.x, v1.y, p.x, p.y);
if (c13 = c32) and (c32 = c24) and (c24 = c41) then
begin
{2) проверката става с насочени лица}
lastx := p.x;
lasty := p.y;
dist := 0;
exit;
end;
res := 1E10; {1E10 ~= inf}
ux14 := v4.y - v1.y;
uy14 := -(v4.x - v1.x);
{u14 - вектор ортогонален на страната v4 v1,
забележете как за създаването на вектора се използва само v1 и v4
това е полезно когато трябва да се създаде вектор само по два върха и
се доказва много лесно с тригонометрия}
ux13 := v3.y - v1.y;
uy13 := -(v3.x - v1.x);
{u13 - вектор ортогонален на страната v3 v1}
if cw(p.x, p.y, p.x + ux14, p.y + uy14, v1.x, v1.y) *
cw(p.x, p.y, p.x + ux14, p.y + uy14, v4.x, v4.y) = -1 then
begin
{3.1 - най-близката пресечна точка е или вътрешна за v1 v4 или
вътрешна v2 v3}
wx := v4.x - v1.x;
wy := v4.y - v1.y;
inter(p.x, p.y, v4.x, v4.y, ux14, uy14, wx, wy, intx, inty);
res := distance(intx, inty, p.x, p.y);
lastx := intx;
lasty := inty;
inter(p.x, p.y, v3.x, v3.y, ux14, uy14, wx, wy, intx, inty);
if distance(intx, inty, p.x, p.y) < res then
begin
res := distance(intx, inty, p.x, p.y);
lastx := intx;
lasty := inty;
end;
dist := res;
exit;
end;
if cw(p.x, p.y, p.x + ux13, p.y + uy13, v1.x, v1.y) *
cw(p.x, p.y, p.x + ux13, p.y + uy13, v3.x, v3.y) = -1 then
begin
{3.1 - най-близката пресечна точка е или вътрешна за v1 v3 или
вътрешна v2 v4}
wx := v3.x - v1.x;
wy := v3.y - v1.y;
inter(p.x, p.y, v3.x, v3.y, ux13, uy13, wx, wy, intx, inty);
res := distance(intx, inty, p.x, p.y);
lastx := intx;
lasty := inty;
inter(p.x, p.y, v2.x, v2.y, ux13, uy13, wx, wy, intx, inty);
if distance(intx, inty, p.x, p.y) < res then
begin
res := distance(intx, inty, p.x, p.y);
lastx := intx;
lasty := inty;
end;
dist := res;
exit;
end;
{3.2) Случая е тривиален, надявам се че не са нужни обяснения}
res := distance(p.x, p.y, v1.x, v1.y);
lastx := v1.x;
lasty := v1.y;
if distance(p.x, p.y, v2.x, v2.y) < res then
begin
res := distance(p.x, p.y, v2.x, v2.y);
lastx := v2.x;
lasty := v2.y;
end;
if distance(p.x, p.y, v3.x, v3.y) < res then
begin
res := distance(p.x, p.y, v3.x, v3.y);
lastx := v3.x;
lasty := v3.y;
end;
if distance(p.x, p.y, v4.x, v4.y) < res then
begin
res := distance(p.x, p.y, v4.x, v4.y);
lastx := v4.x;
lasty := v4.y;
end;
dist := res;
end;
{Намира останалите 2 върха на s по дадените 2}
procedure determine(var s : Tsq);
var v1, v2, v3, v4 : Tpoint;
base, a, b : extended;
begin
v1.x := s.x1; {A}
v1.y := s.y1;
v2.x := s.x2; {D}
v2.y := s.y2;
base := theta(v2.x - v1.x, v2.y - v1.y);
{base := ъгловата част на D спрямо A}
b := distance(v1.x, v1.y, v2.x, v2.y);
a := sqrt( sqr(b) / 2 );
{a := страната на квадрата}
v3.x := v1.x + cos(base + pi / 4) * a; {B}
v3.y := v1.y + sin(base + pi / 4) * a;
v4.x := v1.x + cos(base - pi / 4) * a; {C}
v4.y := v1.y + sin(base - pi / 4) * a;
s.x3 := v3.x;
s.y3 := v3.y;
s.x4 := v4.x;
s.y4 := v4.y;
end;
procedure solve;
var i, j : longint;
tmp : Trec;
begin
for i := 1 to n do
begin
determine(SQ[i]);
A[i].id := i;
A[i].dist := dist(SQ[i]);
end;
{забележете, че по долу реал числата не се сравняват директно, което е много
важно}
for i := 1 to n-1 do
for j := i+1 to n do if (A[j].dist + eps < A[i].dist) or
( (abs(A[j].dist - A[i].dist) < eps) and (A[j].id < A[i].id) ) then
begin
tmp := A[j];
A[j] := A[i];
A[i] := tmp;
end;
end;
{инициализация на графиката}
procedure init;
var i : longint;
begin
tx := p.x;
ty := p.y;
maxx := p.x;
maxy := p.y;
for i := 1 to n do
begin
if SQ[i].x1 < tx then tx := SQ[i].x1;
if SQ[i].y1 < ty then ty := SQ[i].y1;
if SQ[i].x2 < tx then tx := SQ[i].x2;
if SQ[i].y2 < ty then ty := SQ[i].y2;
if SQ[i].x3 < tx then tx := SQ[i].x3;
if SQ[i].y3 < ty then ty := SQ[i].y3;
if SQ[i].x4 < tx then tx := SQ[i].x4;
if SQ[i].y4 < ty then ty := SQ[i].y4;
if SQ[i].x1 > maxx then maxx := SQ[i].x1;
if SQ[i].y1 > maxy then maxy := SQ[i].y1;
if SQ[i].x2 > maxx then maxx := SQ[i].x2;
if SQ[i].y2 > maxy then maxy := SQ[i].y2;
if SQ[i].x3 > maxx then maxx := SQ[i].x3;
if SQ[i].y3 > maxy then maxy := SQ[i].y3;
if SQ[i].x4 > maxx then maxx := SQ[i].x4;
if SQ[i].y4 > maxy then maxy := SQ[i].y4;
end;
if maxx = tx then maxx := tx + 1;
if maxy = ty then maxy := ty + 1;
scale := 639 / (maxx - tx);
if 479 / (maxy - ty) < scale then scale := 479 / (maxy - ty);
{tx, ty - транслация по x и по y,
scale - нужното скалиране за да се вижда всичко}
end;
function scx(x : extended) : longint;
begin
scx := round((x - tx) * scale);
end;
function scy(y : extended) : longint;
begin
scy := round((y - ty) * scale);
end;
procedure drawini;
var
i, l : longint;
begin
initgraph(gd, gm, bgipath);
circle(scx(p.x), scy(p.y), 10);
for i := 1 to n do
begin
line(scx(SQ[i].x1), scy(SQ[i].y1), scx(SQ[i].x3), scy(SQ[i].y3));
line(scx(SQ[i].x1), scy(SQ[i].y1), scx(SQ[i].x4), scy(SQ[i].y4));
line(scx(SQ[i].x2), scy(SQ[i].y2), scx(SQ[i].x3), scy(SQ[i].y3));
line(scx(SQ[i].x2), scy(SQ[i].y2), scx(SQ[i].x4), scy(SQ[i].y4));
end;
for l := 1 to n do
begin
i := A[l].id;
dist(SQ[i]);
circle(scx(p.x), scy(p.y), 10);
line(scx(p.x), scy(p.y), scx(lastx), scy(lasty));
circle(scx(lastx), scy(lasty), 4);
{readkey;}
asm
mov ax, 0
int $16
end; {crt-то не бачка на Athlon 700mhz !}
end;
closegraph;
end;
begin
indata;
{$IFDEF DRAWGFX}
init;
{$ENDIF}
solve;
{$IFDEF DRAWGFX}
drawini;
{$ENDIF}
outdata;
end.
Надявам се, че всеки който разгледа source-а ще забележи колко много разчитам
на графиката за да си помогна в процеса на дебъгване, мисля че липсата на
графични библиотеки към компилаторите е абсурдна, и дискриминира хората,
които имат нужда от тях. На НОИ тази година първоначалната информация беше,
че графичните библиотеки са "орязани", което събуди недоволство в много хора.
За щастие когато започна олипиадата се видя, че всъшност ги има, надявам се
това да продължи и за напред, тоест да има графични библитотеки, което е
напълно нормално желание -- дори самото орязване на компилатора поставя със-
тезателите в лошо положение. Няма как някои да знае каква част от компилатора
ще орязана.