Pagini recente » Cod sursa (job #3235874) | Cod sursa (job #2579259) | Cod sursa (job #1213468) | Cod sursa (job #2541464) | Cod sursa (job #624232)
Cod sursa(job #624232)
#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 Distance(point A,point B){ return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));}
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();
//if two points have the same sloap, delete the one closest to the starting point
int j;
for (i=1;i<N-1;i++)
if (sloap[i]==sloap[i+1])
{
if (Distance(arrayOfPoints[0],arrayOfPoints[i]) > Distance(arrayOfPoints[0],arrayOfPoints[i+1])) j = i+1;
else j=i;
for (;j<N-1;j++)
{
arrayOfPoints[j] = arrayOfPoints[j+1];
sloap[j] = sloap[j+1];
}
N--;
}
//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> sol;
sol.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) {sol.push_back(arrayOfPoints[pos]);i++;}
else {sol.push_back(arrayOfPoints[1]);i=2;}
sol.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 = sol.size();
while (top-3 >= 0 &&
sol[top-2].x*sol[top-1].y + sol[top-1].x*arrayOfPoints[i].y + arrayOfPoints[i].x*sol[top-2].y - sol[top-2].y*sol[top-1].x - sol[top-1].y*arrayOfPoints[i].x - arrayOfPoints[i].y*sol[top-2].x < 0)
{sol.pop_back();top--;}
sol.push_back(arrayOfPoints[i]);
}
//print the points on the convex envelope
freopen ("infasuratoare.out","w",stdout);
//printf("%d \n", N);
top = sol.size();
printf ("%d \n",top);
for (i=0;i<top;i++)
printf("%lf %lf\n", sol[i].x,sol[i].y);
fclose(stdout);
return 0;
}