Pagini recente » Cod sursa (job #1578724) | Cod sursa (job #453224) | Cod sursa (job #233948) | Cod sursa (job #2364682) | Cod sursa (job #2641768)
#include <stdio.h>
#include <algorithm>
#include <stack>
#define NMAX 120005
using namespace std;
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
struct punct {double x; double y;} p[NMAX];
int n,vf,stiva[NMAX],i,imin;
double xmin,ymin;
bool comparare(punct A, punct B)
{
if((A.y - ymin)*(B.x - xmin) <= (A.x - xmin) * (B.y - ymin))
return 1;
return 0;
}
bool turn(double x1, double y1, double x2, double y2, double x3, double y3)
{
return ((x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) > 0);
}
int main()
{
fscanf(fin, "%d", &n);
ymin = 1e9;
for(i=1; i<=n; ++i)
{
fscanf(fin, "%lf%lf", &p[i].x, &p[i].y);
if(p[i].y < ymin)
{
ymin = p[i].y;
imin = i;
}
else
if(p[i].y == ymin and p[i].x < p[imin].x)
imin = i;
}
xmin = p[imin].x;
swap(p[1],p[imin]);
stable_sort(p+1, p+n+1, comparare);
stiva[1] = 1;
stiva[2] = 2;
vf = 2;
for(i=3; i<=n; ++i)
{
while(vf>=2 and !turn(p[stiva[vf-1]].x, p[stiva[vf-1]].y, p[stiva[vf]].x, p[stiva[vf]].y, p[i].x, p[i].y)) //0->right, 1->left
vf--;
vf++;
stiva[vf] = i;
}
fprintf(fout, "%d\n", vf);
fprintf(fout, "%lf %lf\n", p[stiva[vf]].x, p[stiva[vf]].y);
for(i=1; i<=vf-1; ++i)
fprintf(fout, "%lf %lf\n", p[stiva[i]].x, p[stiva[i]].y);
fclose(fin);
fclose(fout);
return 0;
}