PREE01 - Editorial

editorial
, , ,
1

Problem Link:

Contest

Difficulty:

Medium

Pre-Requisites:

Geomatry

Problem:

Find minimum length of rope to cover the boundary of all the trees located in a garden

Explaination:

This is simple famous convex hull problem. To read about that click here.

You will have to use a structure:

struct Point
{
    double x;
    double y;
};

First sort all points and find the bottom most point and keep it at first index of array of Points.

Then Sort other n-1 points with respect to the first point. A point p1 comes before p2 in sorted ouput if p2 has larger polar angle (in counterclockwise direction) than p1.

Then Create an empty stack and push first three points to it. Process remaining n-3 points. Keep removing top while the angle formed by points next-to-top, top, and points[i] makes a non-left turn which can be checked by area of triangle which will be negative for a left turn.
By now the stack have the output points, i.e. points of vertices of hull. Just calculate parameter of triangle and print the answer.

Here is actual code:

#include &ltcstdio&gt
#include &ltiostream&gt
#include &ltmath.h&gt
#include &ltstack&gt
#include &ltstdlib.h&gt
using namespace std;

double sum=0;
double s;
double l=0,w=0;

struct Point
{
    double x;
    double y;
};

Point p0;

Point nextToTop(stack&ltPoint&gt &S)
{
    Point p = S.top();
    S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}

void swap(Point &p1, Point &p2)
{
    Point temp = p1;
    p1 = p2;
    p2 = temp;
}

double dist(Point p1, Point p2)
{
    return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

int orientation(Point p, Point q, Point r)
{
    double val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0.0) return 0;
    return (val > 0)? 1: 2;
}

int compare(const void *vp1, const void *vp2)
{
   Point *p1 = (Point *)vp1;
   Point *p2 = (Point *)vp2;

   int o = orientation(p0, *p1, *p2);
   if (o == 0)
     return (dist(p0, *p2) >= dist(p0, *p1))? -1 : 1;

   return (o == 2)? -1: 1;
}

void convexHull(Point points[], int n)
{
   double ymin = points[0].y;
   int  min = 0;
   for (int i = 1; i &lt n; i++)
   {
     double y = points[i].y;
     if ((y &lt ymin) || (ymin == y && points[i].x &lt points[min].x))
        {ymin = points[i].y;
          min = i;}
   }

   swap(points[0], points[min]);

   p0 = points[0];
   qsort(&points[1], n-1, sizeof(Point), compare);
   stack&ltPoint&gt S;
   S.push(points[0]);
   S.push(points[1]);
   S.push(points[2]);

   for (int i = 3; i &lt n; i++)
   {
      while (orientation(nextToTop(S), S.top(), points[i]) != 2)
         S.pop();
      S.push(points[i]);
   }

  Point m=S.top();
  l=m.x;
  w=m.y;  
  while (!S.empty())
   {
       Point p = S.top();
       s=sqrt(pow(p.x-l,2)+pow(p.y-w,2));
       sum=sum+s;
       l=p.x;
       w=p.y;
       S.pop();
   }
   S.push(m);
   Point p = S.top();
   s=sqrt(pow(p.x-l,2)+pow(p.y-w,2));
   sum+=s; 
   printf("%.2lf\n",sum);
}
int main()
{  
    int t,n;
    Point points[2000];
    cin &gt&gt t;
    while(t--)
    { cin &gt&gt n; 
    w=0;l=0;sum=0;s=0; 
    for(int i=0;i&lt=n-1;i++)
    {
    cin >> points[i].x;
    cin>>points[i].y;
    }
    convexHull(points, n);
  }
  return 0;
}