Cod sursa(job #1427046)

Utilizator radu_uniculeu sunt radu radu_unicul Data 1 mai 2015 13:45:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <cstdio>
#include <stack>
#include <stdlib.h>
using namespace std;
    FILE *fin,*fout;
struct Point
{
    float x;
    float y;
};
Point p0;
Point nextToTop(stack<Point> &S)
{
    Point p = S.top();
    S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}
int swap(Point &p1, Point &p2)
{
    Point temp = p1;
    p1 = p2;
    p2 = temp;
}
float 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)
{
    float val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}
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)
{
   int ymin = points[0].y, min = 0;
   for (int i = 1; i < n; i++)
   {
     float y = points[i].y;
     if ((y < ymin) || (ymin == y && points[i].x < 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<Point> S;
   S.push(points[0]);
   S.push(points[1]);
   S.push(points[2]);
   for (int i = 3; i < n; i++)
   {
      while (orientation(nextToTop(S), S.top(), points[i]) != 2)
    S.pop();
      S.push(points[i]);
   }
   fprintf(fout,"%d\n",S.size());
   while (!S.empty())
   {
       Point p = S.top();
       fprintf(fout,"%f %f\n",p.x,p.y);
       S.pop();
   }
}
int main()
{
    fin=fopen("infasuratoare.in","r");
    fout=fopen("infasuratoare.out","w");
    int n;
    fscanf(fin,"%d",&n);
    Point points[n];
    for(int i=0;i<n;i++) fscanf(fin,"%f%f",&points[i].x,&points[i].y);
    convexHull(points, n);
    return 0;
}