Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #768115)
Cod sursa(job #768115)
#include<stdio.h>
#define absv(A) ((A) >= 0 ? (A) : -(A))
FILE *in, *out;
double point[120000][2], minX, minY;
int N, heapSize, firstPoint, stack[120000], stSize;
int ifSwap(int i, int j)
{
/*they have same X coord i.e. slope is infinity*/
if(point[i][0] == minX && point[j][0] == minX)
{
/*i point is higher on Y axis than j point*/
if(point[i][1] > point[j][1]) return 1;
else return 0;
}
else if(point[i][0] == minX)
{
return 1;
}
else if(point[j][0] == minX)
{
return 0;
}
else
{
long double slopeI, slopeJ;
slopeI = ((point[i][1] - minY)/(point[i][0] - minX));
slopeJ = ((point[j][1] - minY)/(point[j][0] - minX));
//printf("%Lf %Lf %Lf\n", point[i][0], point[i][1], slopeI);
//printf("%Lf %Lf %Lf\n", point[j][0], point[j][1], slopeJ);
/*if the slope of min with point i is greater than with point j*/
if(slopeI > slopeJ) return 1;
/*if the slopes are equal we pick the closest point to min*/
else if(slopeI == slopeJ && point[i][0] > point[j][0]) return 1;
else return 0;
}
}
void heapify(int pos)
{
int next = pos;
long double aux;
for(;;)
{
if((pos<<1) <= heapSize && ifSwap(next, (pos<<1)))
next <<= 1;
if((pos<<1)+1 <= heapSize && ifSwap(next, (pos<<1)+1))
next = (pos<<1)+1;
if(next == pos) break;
aux = point[pos][0]; point[pos][0] = point[next][0]; point[next][0] = aux;
aux = point[pos][1]; point[pos][1] = point[next][1]; point[next][1] = aux;
pos = next;
}
}
int popHeap()
{
long double aux;
aux = point[1][0]; point[1][0] = point[heapSize][0]; point[heapSize][0] = aux;
aux = point[1][1]; point[1][1] = point[heapSize][1]; point[heapSize][1] = aux;
heapSize--;
heapify(1);
return heapSize+1;
}
int main()
{
int i;
long double aux;
in = fopen("infasuratoare.in", "r");
out = fopen("infasuratoare.out", "w");
/*reading input data*/
fscanf(in, "%d", &N);
for(i = 0; i < N; ++i)
fscanf(in, "%lf %lf", &point[i][0], &point[i][1]);
/*done reading data*/
/*finding leftmost point*/
minX = minY = (1 << 30);
for(i = 0; i < N; ++i)
if(point[i][0] < minX || (point[i][0] == minX && point[i][1] < minY))
minX = point[i][0],
minY = point[i][1],
firstPoint = i;
/*found leftmost point*/
/*creating a minheap*/
aux = point[0][0]; point[0][0] = point[firstPoint][0]; point[firstPoint][0] = aux;
aux = point[0][1]; point[0][1] = point[firstPoint][1]; point[firstPoint][1] = aux;
heapSize = N-1;
for(i = heapSize>>1; i; --i)
heapify(i);
/*done*/
/*finding the convex hull*/
stack[0] = 0;
while(heapSize)
{
i = popHeap();
while(stSize && (point[stack[stSize-1]][0]*(point[stack[stSize]][1]-point[i][1]) +
point[stack[stSize]][0]*(point[i][1]-point[stack[stSize-1]][1]) +
point[i][0]*(point[stack[stSize-1]][1]-point[stack[stSize]][1])) < 0)
stSize--;
stack[++stSize] = i;
}
/*done*/
fprintf(out, "%d\n", stSize+1);
for(i = 0; i <= stSize; ++i)
fprintf(out, "%lf %lf\n", point[stack[i]][0], point[stack[i]][1]);
fclose(in);
fclose(out);
return 0;
}