BOOI 3 - Wall
Уловието на задачата може да прочетете
тук.
Решение
За да се намери отговорът на поставената задача, първо е необходимо да се намери
обхващащата обвивка на точките от зададения многоъгълник. След това, ако се
построи кривата, която във всеки един момент е на разстояние Lот най-близката точка от обвивката, тя
ще има минимална дължина и ще отговаря на условието на краля.
Обвивката може да се построи със сложност O(NlogN). Избира се точка
M, която има най-малка y-координата, а ако има няколко с
най-малката такава се избира тази, която има най-малка x-координата. Нека има точка X, която има същата y-координата като M, а x-координатата и е безкрайно голяма. Останалите точки се сортират по намаляващ
ъгъл XMPi, като Pi е
i-та точка. След това в обвивката се
поставят точката Mи първата от сортираната
последователност. Точките се добавят към обвивката в реда, в който са след
сортирането. Когато една точка Piсе добави към обвивката за нея и за
предишните две добавени се проверява дали не нарушават изпъкналостта. Ако я
нарушават, предпоследната добавена в обвивката се премахва. Тази проверка се
прави докато последните три точки в обвивката не нарушават изпъкналостта. На
фигурата долу може да се види как ако точките D,C и B са добавени към обвивката и след това
се добави точката A, точките B и C ще бъдат изключени. Това става, защото C,
B и A зададени в този
ред нарушават изпъкналостта и точката B се премахва. Същото ще се получи и с
точката C на следващата стъпка. Следва да се забележи, че за тази задача, когато
три точки са на една права и са от обвивката няма смисъл да се добавя тази,
която е между другите две. Ето защо от точките, които са с равен ъгъл XMPi, следва да се разглежда само тази,
която е най-далече от точката M. Другите със сигурност не са в
обвивката.
Сега остава да се построи крива, която да минава
във всеки един момент на разстояние Lот най-близката точка от обвивката. Нека точките
в обвивката са a1,
a2, a3,…, an.
За всяка
точка от обвивката се издигат два външни за обвивката перпендикуляра с дължина L, за
всяка от двете отсечки, които имат общ край в тази точка. Нека за aiдругият
край на двата перпендикуляра е ai’и ai’’. Ако
се свържат всички ai’’с ai+1’ и също така an’’ с a1’ще се получат отсечки,
чиято обща дължина е колкото периметъра на обвивката. Също така всяка точка от
тези отсечки е на разстояние Lот най-близката точка от обвивката. Между всеки
две точки ai’и ai’’се построява дъга с
радиус Lи център
точката ai
. Следователно
всички точки от тази дъга са на разстояние Lот обвивката. Дъгите
образувани по този начин са части от една окръжност с радиус L.За всеки
връх от обвивката се построява дъга с ъгъл 180 – α, като α е ъгълът в обвивката при този връх.
Ако обвивката има n върха, сумата от ъглите, съпоставени на дъгите е
n*180 – (n-2)*180 = 360,
тъй като сумата от ъглите на многоъгълника е (n-2)*180. Оттук се вижда, че дъгите образуват
окръжност с радиус L.
Получената крива изпълнява условията на краля. Дължината
и е равна на сумата на периметъра на обвивката и дължината на окръжност с
радиус L.
Примерна реализация
/*
TASK:wall
LANG:C++
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 5008
struct tpoint
{
int x,y;
};
// the number of points and the radius
int n,r;
// the number of points int the hull
int hullbr;
// the points in the hull
tpoint hull[MAXN];
// all the points in the input
tpoint points[MAXN];
int tarea;
// calculates the area of a triangle
int calcArea(tpoint p1, tpoint p2, tpoint p3)
{
return p1.x*(p2.y-p3.y) + p2.x*(p3.y-p1.y) + p3.x*(p1.y-p2.y);
}
int cmp(const void *e1, const void *e2)
{
tarea = calcArea(points[0],*((tpoint*)e1),*((tpoint*)e2));
if(tarea!=0)
return tarea;
else
if(((tpoint*)e1)->y != ((tpoint*)e2)->y)
return ((tpoint*)e2)->y - ((tpoint*)e1)->y;
else
return ((tpoint*)e2)->x - ((tpoint*)e1)->x;
}
void input()
{
int i;
scanf("%d %d",&n,&r);
for(i=0;i<n;i++)
{
scanf("%d %d",&points[i].x,&points[i].y);
}
}
// makes the hull for the given points
void makeHull()
{
int i,i2;
tpoint buf;
hull[0] = points[0];
points[n] = points[0];
hull[1] = points[1];
hullbr = 2;
// goes through all the points and add them to the hull
for(i=2;i<=n;i++)
{
if(calcArea(points[0],points[i-1],points[i])==0 && i!=n)
continue;
hull[hullbr++] = points[i];
// tries to remove previously added points
while(hullbr>2 &&
calcArea(hull[hullbr-3],hull[hullbr-2],hull[hullbr-1])>=0)
{
hull[hullbr-2] = hull[hullbr-1];
hullbr--;
}
}
hullbr--;
// the lenght of the circle with radius r
double sum=3.14159265*r*2;
// sums the length of the hull
for ( int i=0 ; i<hullbr-1 ; i++ ) {
sum+=hypot(hull[i].x-hull[i+1].x,hull[i].y-hull[i+1].y);
}
sum+=hypot(hull[hullbr-1].x-hull[0].x,hull[hullbr-1].y-hull[0].y);
printf("%.0lf\n",sum);
}
void solve()
{
int i;
tpoint best;
int ind;
best = points[0];
ind = 0;
// finds the lowest point, and from all the
// lowest points takes the leftmost one
for(i=1;i<n;i++)
{
if(best.y>points[i].y || (best.y==points[i].y && best.x>points[i].x))
{
best = points[i];
ind = i;
}
}
points[ind] = points[0];
points[0] = best;
// sorts the points by angle
qsort(points+1,n-1,sizeof(tpoint),cmp);
makeHull();
}
int main()
{
input();
solve();
return 0;
}
Автор: Антон Димитров
обратно към текущ брой
|