Есенен турнир 2004, Задача А1. СЕЛА
Уловието на задачата може да прочетете
тук.
Решение
Решението на задачата може да
бъде разделено на две части – намиране на изпъкнала обвивка на точки в
равнината, защото именно тя има минимален приметър сред тези криви, които
обграждат всички точки и след това намиране на разстоянието между двете
най-близки точки в равнината изключвайки тези от обвивката.
По долу
е описан алгоритъм за построяване на изпъкнала обвивка със сложност O(NlogN).
Избира
се една точка, която е с най-малка yкоордината. Ако има няколко такива
точки, избираме тази с най-голямаx кооордината. Нека
тази точка е M и нека е
дефинирана точка X, която има
същата yкоордината като М
и х координата по-голяма от тази на M. Нека
останалите точки освен М са P1,
P2, ..., Pn
.
Сортират
се по ъгъла ХМ
Piв нарастващ ред.
Ако
две точки са с равни ъгли ХМРiсе сортират по
отдалеченост от точката М в нарастващ
ред. Ако първите К (като К > 1) точки в сортираната
последователност са с равен ъгъл ХМРi, то те се
нареждат изкуствено като първо стои тази, която е най-близко до М, т.е. обратно на сортираната
последователност. Това се налага, защото иначе ще се получи неправилна обвивка,
а именно от тези първи К точки в
обвивката ще влезе само тази, която е най-близо до М, а е очевидно, че те
всички трябва да са в обвивката. От там нататък се прилага следния подход за
построяване на обвивката. След като в началото са добавени поне 2 точки, добавя
се следващата точка от сортираната последователност като следваща точка в
обвивката. Проверява се за последните три добавени точки от обвивката дали не
нарушават изискването за изпъкналост на обвивката. Това се прави като се
пресмята насоченото лице на тези три точки. Нека последните три точки, добавени
в обвивката са R1,R2 и R3, като R3е
последната добавена. Тогава трябва да се изчисли насоченото лице на точките R1,R2 и R3в този
ред. Ако координатите на трите точки са съответно х1 и у1,
х2 и у2, х3
и у3, за да се изчисли насоченото
им лице в този ред R1, R2, R3,
трябва да се пресметне стойността на израза х1*(у2 -
у3) + х2*(у3 - у1) + х3*(у1
- у2).
Така
всъщност се получава удвоеното лицето на тригълника, определен от трите точки
като освен това полученото число може да бъде положително или отрицателно в
зависимост от това дали трите точки са зададени по часовниковата стрелка
(насоченото лице е отрицателно) или обратно на часовниковата стрелка
(насоченото лице е положително). В случая с обвивката се изисква последните три
точки, които са включени да са обратно на часовниковата стрелка, за да не се
нарушава условието за изпъкналост на обвивката. Т.е. насоченото лице трябва да
е положително. Ако насоченото лице е отрицателно, то следва, че предпоследната
добавена точка не е от обвивката и трябва да се извади. Така последната
добавена точка застава на нейното място в обвивката.Сега се
проверява дали така получените три последни точки от обвивката не нарушават
условието за нейната изпъкналост. И това се прави докато последните три точки
от обвивката имат положително насочено лице взето в реда, в който са в
обвивката (т.е. не нарушават изпъкналостта на обвивката). Не е възможно да
останат само две точки в обвивката по този начин понеже още в самото начало е
включена тази с най-малка у
координата и тази с най-малък ъгъл, а те винаги са от обвивката и няма
верояаност да бъдат изключени на някоя стъпка от алгоритъма. Така след краен
брой стъпки всички точки от сортираната последователност са обходени и в крайна
сметка е построена обвивката. Сложността на този алгоритъм е О(NlogN), което е
подходящо за тази задача.
Сега остава и втората част от
решението, а именно намирането на разстоянието между двете най-близки точки от
множество от точки в равнината. След като се намери обвивката на точките се
отделят тези, които не са в нея и за тях прилагаме алгоритъма, който е описан
по-долу и има сложност O(NlogN). Този алгоритъм
се основава на техниката “Разделяй и владей”. Накратко идеята му е да сортираме
точките по х координата, а тези с
равна х коорината се сортират по у координата и да ги разделим на две подмножества
с по равен брой елементи или ако точките са нечетен брой на едно множество с Lелемента
и едно с L+1елемента. Точките в първото множество са от първата
половина на сортираната последователност по х
координата, а точките от второто са от втората половина. Нека приемем, че можем
да намерим двете най-близки точки от множеството точки. Тогава се намират двете
най-близки в първото множество и двете най-близки във второто множество. Нека те
са на разстояния съответно d1иd2. Нека d = min(d1, d2). Тогава двете най-близки от всички точки
са или на разстояние dи са в едно и също подмножество или са
в различни подмножества. Сега трябва да се провери случая, когато двете точки
са в различни подмножества. Тогава ако се вземе една вертикална права p
с х координата,
такава че да разделя двете подмножества, то двете най-близки точки такива, че
да са в различни подмножества ще са на разстояние не по-големи от
dот тази
вертикална права. Сега е нужно да се вземат точките на разстояние не по-голямо
от d
oтp сортирани по у координата и където има точки с равни у координати са сортирани по х
координата, нека това множество е F. Това може да
се постигне ако освен сортирани по х
се пази списък с точките, сортирани и по у
координата. На този етап остава да се проверява за всяка точка от Fна
какво разстояние е от всяка друга точка и да се вземат двете най-близки и
резултата да се сравни с d. Но това довежда до алгоритъм със
сложност O(N2). За целта се използва едно твърдение,
чието доказателство няма да предоставим тук, но може да бъде намерено на много
места. Това твърдение е, че за всяка точка от множеството F, сортирано
по у координата за всяка точка трябва да се търси разстоянието само до
следващите седем точки в сортираната последователност. Това ни гарантира, че
сме проверили всички точки, които могат да са най-близки в множеството F. Сега
ако двете най-близки точки от Fса на разстояние h, то се
взема min(d,h) и това е
разстоянието между двете най-близки точки в цялото множество от точки. Този
подход може да се приложи, за да се намери разстоянието между двете най-близки
точки въс всяко от двете подмножества и така да се продължава докато в
подмножествата, на които разделяме останат две или три точки, за които лесно
намираме двете най-близки.
Така в
крайна сметка се получава решение със сложност O(NlogN), което при
ограничението от N<20000 работи
достатъчно бързо.
Примерна реализация:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 20010
#define MAXP 20010
#define MAXL 21
#define DEPTH 7
#define INF 2000000000
#define EPS 0.000000000001
typedef struct s1
{
int x,y;
} tdpoint;
int n;
int mytmp;
tdpoint mas[MAXN];
// tuk se paziat vsichki tochki ot vhoda
int count;
// broja na tochkite, koito ne vlizat v obvivkata
tdpoint points[MAXP];
// tuk se paziat tochkite, koito ne vlizat v obvivkata
double answer;
// otgovora
double tmp2;
int hull[MAXN];
// tuk se paziat tochkite vkliucheni v obvivkata
int used[MAXN];
// pokazva koi tochki sa izpolvani v obvivkata
int brh;
// broj tochki v obvivkata
tdpoint levels[MAXL][2][MAXN];
// tova sa masivite nuzhni za Divide and
// Conquer-a, za da se paziat tochkite
// sortirani po y koordinatata
double beg;
void input()
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d %d",&mas[i].x,&mas[i].y);
}
double Dist(int x1, int y1, int x2, int y2)
// funkcia, koiato smiata razstoianie m/u 2 tochki
{
double r1,r2;
r1 = (double)(x1-x2);
r2 = (double)(y1-y2);
return sqrt(r1*r1 + r2*r2);
}
int FindArea(tdpoint p1, tdpoint p2, tdpoint p3)
// namira nasocheni lice na 3 tochki
{
double tmp;
double x1,y1,x2,y2,x3,y3;
x1 = p1.x;
y1 = p1.y;
x2 = p2.x;
y2 = p2.y;
x3 = p3.x;
y3 = p3.y;
tmp = x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2);
if(tmp<0)
return -1;
else
if(tmp>0)
return 1;
else return 0;
}
int cmpia(const void *e1,const void *e2)
// fukcia za sortirane na tochkite po ygyl, izpolzva nasocheno lice
{
mytmp = FindArea(mas[0],(*((tdpoint*)e1)),(*((tdpoint*)e2)));
if(mytmp==0)
if(((tdpoint*)e2)->y!=((tdpoint*)e1)->y)
return ((tdpoint*)e2)->y - ((tdpoint*)e1)->y;
else return ((tdpoint*)e1)->x - ((tdpoint*)e2)->x;
else
return (-mytmp);
}
int cmpdx(const void *e1, const void *e2)
// sortira tochki po x koordinata
{
if(((tdpoint*)e1)->x==((tdpoint*)e2)->x)
return ((tdpoint*)e1)->y - ((tdpoint*)e2)->y;
else
return ((tdpoint*)e1)->x - ((tdpoint*)e2)->x;
}
int cmpdy(const void *e1, const void *e2)
// sortira tochki po y koordinata
{
if(((tdpoint*)e1)->y==((tdpoint*)e2)->y)
return ((tdpoint*)e1)->x - ((tdpoint*)e2)->x;
else
return ((tdpoint*)e1)->y - ((tdpoint*)e2)->y;
}
double ClosestOf3(int l)
// namira naj-blizki sred 3 tochki
{
double r1;
double min;
min = Dist(points[l].x,points[l].y,points[l+1].x,points[l+1].y);
r1 = Dist(points[l].x,points[l].y,points[l+2].x,points[l+2].y);
if(min>r1)
min = r1;
r1 = Dist(points[l+1].x,points[l+1].y,points[l+2].x,points[l+2].y);
if(min>r1)
min = r1;
return min;
}
double FindClosestTwoPoints(int l, int r, int lev, int ind)
// funkcia za namirane na 2-te naj-blizki
// tochki chrez metoda "Razdeliaj i Vladej"
{
int i,i2;
int midel;
int brel;
int midx,midy;
int br1,br2;
double res;
double delta;
double vertline;
int brnl;
if(r-l==2) // ako tochkite sa 3
{
return ClosestOf3(l);
}
if(r-l==1) // ako tochkite sa 2
{
return Dist(points[l].x,
points[l].y,
points[l+1].x,
points[l+1].y);
}
midel = (l+r)/2;
brel = r-l+1;
midx = points[midel].x;
midy = points[midel].y;
br1 = br2 = 0;
vertline = ((double)(points[midel+1].x + points[midel].x))/2.0;
// tova e vert. linia m/u dvete mnojestva ot tochki
for(i=0;i<brel;i++)
{
if(levels[lev][ind][i].x<midx ||
(levels[lev][ind][i].x==midx &&
levels[lev][ind][i].y<=midy))
//ako tochkata e za pyrvoto podmnozhestvo
{
levels[lev+1][0][br1++] = levels[lev][ind][i];
}
else // ako tochkata e za vtoroto podmnozhestvo
{
levels[lev+1][1][br2++] = levels[lev][ind][i];
}
}
res = FindClosestTwoPoints(l,midel,lev+1,0);
// otiva kym sledvashtoto nivo
// na rekursiata za pyrvoto podmnozhestvo
delta = res;
res = FindClosestTwoPoints(midel+1,r,lev+1,1);
// otiva kym sledvashtoto nivo
// na rekursiata za vtoroto podmnozhestvo
if(delta>res)
// namira razstoianieto m/u dvete naj-blizki
// tochki v edno ot dvete podmnozhestva
delta = res;
brnl = 0;
for(i=0;i<brel;i++)
// konstruirame mnozhestvoto ot tochki
// na razstoianie ne po-goliamo
// ot delta ot razdeliashtata vert. linia - vertline
{
if(fabs((double)
(levels[lev][ind][i].x)-vertline)<=delta)
{
levels[lev][ind][brnl] = levels[lev][ind][i];
brnl++;
}
}
for(i=0;i<brnl;i++) // za vsiaka tochka
{
for(i2=1;i2<=DEPTH&&i+i2<brnl;i2++)
// gledame sledvashtite 7 tochki v
{
// sortiranata posledovatelnost
res = Dist(levels[lev][ind][i].x,
levels[lev][ind][i].y,
levels[lev][ind][i+i2].x,
levels[lev][ind][i+i2].y);
if(delta>res)
delta = res;
}
}
return delta; // tuk se sydyrzha razstoianieto
// m/u dvete naj-blizki tochki v razglezhdanoto mnozhestvo
}
void MakeConvex() // funkcia za postroiavane na obvivka
{
int i;
int maxx,miny,ind;
tdpoint buf;
miny = INF;
for(i=0;i<n;i++) // namirame tazi, koiato ima naj-malka
// y koordinata i naj-goliama
// x koordinata ako ima niakolko
// s ravni naj-malki y koordinati
{
if(mas[i].y<miny)
{
miny = mas[i].y;
maxx = mas[i].x;
ind = i;
}
else
if(mas[i].y==miny && mas[i].x>maxx)
{
maxx = mas[i].x;
ind = i;
}
}
buf = mas[ind];
mas[ind] = mas[0];
mas[0] = buf;
qsort(mas+1,n-1,sizeof(tdpoint),cmpia);
// sortirat se tochkite po ygyl
mas[n] = mas[0];
brh = 1;
hull[0] = 0;
i = 2;
while(FindArea(mas[0],mas[1],mas[i])==0)
// dobaviat se tochkite, koito sa s naj-malyk ygyl i
{
// imat raven ygyl
hull[brh++] = i;
i++;
}
hull[brh] = 1;
brh++;
for(;i<=n;i++)
{
hull[brh] = i;
brh++;
while(FindArea(mas[hull[brh-3]],
mas[hull[brh-2]],mas[hull[brh-1]])<0)
{
// dobaviat se posledovatelno tochkite kym obvivkata
hull[brh-2] = hull[brh-1];
brh--;
}
}
brh--;
for(i=0;i<n;i++)
used[i] = 0;
for(i=0;i<brh;i++)
used[hull[i]] = 1;
count = 0;
for(i=0;i<n;i++)
// namirat se tochkite, koito ne sa v obvivkata
if(!used[i])
{
points[count].x = mas[i].x;
points[count].y = mas[i].y;
count++;
}
}
void solve()
{
int i;
int brp;
MakeConvex(); // pravi se obvivka
qsort(points,count,sizeof(tdpoint),cmpdx);
// sortirat se tochkite po x koordinata
brp = 1;
for(i=0;i<count;i++)
{
levels[0][0][i] = points[i];
}
qsort(levels[0][0],count,sizeof(tdpoint),cmpdy);
// sortirat se tochkite po y koordinata
answer = FindClosestTwoPoints(0,count-1,0,0);
// namirat se dvete naj-blizki tochki
}
void output()
{
printf("%.8lf\n",answer);
}
int main()
{
input();
solve();
output();
return 0;
}
Автор: Антон Димитров
обратно към брой 26
|