Текущ брой на Списание ИнфоМан
 


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;
}

Автор: Антон Димитров


обратно към текущ брой