Pagini recente » Cod sursa (job #659757) | Cod sursa (job #3161880) | Cod sursa (job #1662133) | Cod sursa (job #290885) | Cod sursa (job #624226)
Cod sursa(job #624226)
#include<cstdio>
#include<vector>
#include<cmath>
#define PI 3.14159265
#define inf 1<<30;
using namespace std;
int N;
double sloap[1000000];
struct point
{
double x,y;
};
point arrayOfPoints[1000000];
//compute the sloap/gradient (incline) of the line determined by points A and B
double SloapOfLine(point A, point B)
{
if (B.x == A.x) return -inf;
return (B.y - A.y)/(B.x - A.x);
}
//HeapSort
void PullDown(int i, int n)
{
int fiu,done = 0;
double aux;
point auxPoint;
aux = sloap[i]; auxPoint = arrayOfPoints[i];
while (i<=n/2 && !done)
{
fiu = 2*i;
if (fiu + 1 <= n && sloap[fiu+1] > sloap[fiu]) fiu ++;
if (sloap[fiu] > sloap[i])
{
sloap[i] = sloap[fiu];
arrayOfPoints[i] = arrayOfPoints[fiu];
i = fiu;
}
else done = 1;
sloap[i] = aux;
arrayOfPoints[i] = auxPoint;
}
}
void MinHeap()
{
for (int i = (N-1)/2; i>=1 ;i--) PullDown(i,N-1);
}
void HeapSort()
{
int i;
double aux;
point auxPoint;
for (i = N-1; i >= 2; i--)
if (sloap[1] > sloap[i])
{
aux = sloap[1];
sloap[1] = sloap[i];
sloap[i] = aux;
auxPoint = arrayOfPoints[1];
arrayOfPoints[1] = arrayOfPoints[i];
arrayOfPoints[i] = auxPoint;
PullDown(1,i-1);
}
}
double Angle(point A, point B, point C)
{
double AB, BC, CA, unghiB;
AB = sqrt((B.x-A.x)*(B.x-A.x) + (B.y-A.y)*(B.y-A.y));
CA = sqrt((C.x-A.x)*(C.x-A.x) + (C.y-A.y)*(C.y-A.y));
BC = sqrt((B.x-C.x)*(B.x-C.x) + (B.y-C.y)*(B.y-C.y));
double cosx = (AB*AB + BC*BC - CA*CA)/(2*AB*BC);
unghiB = acos(cosx) * 180.0 / PI;
return unghiB;
}
int main()
{
//read data
freopen ("infasuratoare.in","r",stdin);
scanf ("%d", &N);
int i;
//choose a point which is certainly a point of the convex envelope
//one such point is point witch is the farthest one to the left.
//should more then one point be situatod on the farthest vertical line, the point with the lowest x will be selected
scanf("%lf %lf", &arrayOfPoints[0].x, &arrayOfPoints[0].y);
point tempPt = arrayOfPoints[0];
int pos = 0; //save the position of the temporary starting point
for (i=1;i<N;i++)
{
scanf("%lf %lf", &arrayOfPoints[i].x, &arrayOfPoints[i].y);
if (arrayOfPoints[i].x > tempPt.x || (arrayOfPoints[i].x == tempPt.x && arrayOfPoints[i].y < tempPt.y))
{tempPt = arrayOfPoints[i]; pos = i;}
}
//store the starting point at arrayOfPoints[0];
tempPt = arrayOfPoints[pos];
arrayOfPoints[pos] = arrayOfPoints[0];
arrayOfPoints[0] = tempPt;
fclose(stdin);
//compute the sloap of all line determined by the starting point and any other point
for (i = 1;i < N; i++) sloap[i] = SloapOfLine(arrayOfPoints[0],arrayOfPoints[i]);
//sort the points in the array by the sloap of the line each of them determines along with the starting point
MinHeap();
HeapSort();
//put the first three points on the vector: the starting point and the point highest on the same vertical line
//if such a point exists, or the starting point and the point at the 1st position in the array
//arrayOfPoints[2] is the temporary third point
vector <point> envelope;
envelope.push_back(arrayOfPoints[0]);
i=0;
double maxY = arrayOfPoints[0].y;
while (arrayOfPoints[i+1].x == arrayOfPoints[0].x)
{
if (arrayOfPoints[i+1].y > maxY) maxY = arrayOfPoints[i+1].y;
i++;
pos = i;
}
if (i!=0) {envelope.push_back(arrayOfPoints[pos]);i++;}
else {envelope.push_back(arrayOfPoints[1]);i=2;}
envelope.push_back(arrayOfPoints[2]);
i++;
//add the following points
//if X Y Z are the last three points and X Y T is a greater angle than X Y Z, then pop Z
int top;
for (;i<N;i++)
{
top = envelope.size();
while (top-3 >= 0 && (Angle(envelope[top-3],envelope[top-2],envelope[top-1])< Angle(envelope[top-3],envelope[top-2],arrayOfPoints[i])))
{envelope.pop_back();top--;}
envelope.push_back(arrayOfPoints[i]);
}
//print the points on the convex envelope
freopen ("infasuratoare.out","w",stdout);
//printf("%d \n", N);
top = envelope.size();
printf ("%d \n",top);
for (i=0;i<top;i++)
printf("%lf , %lf \n", envelope[i].x,envelope[i].y);
fclose(stdout);
return 0;
}