Pagini recente » Cod sursa (job #2848106) | Cod sursa (job #3230546) | Cod sursa (job #3145008) | Cod sursa (job #102130) | Cod sursa (job #1881272)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAXN 120010
using namespace std;
struct point
{
double x, y;
};
int st[MAXN];
int used[MAXN];
int urmator, dir;
int vf;
int n;
point puncte[MAXN];
bool how(point a, point b)
{
if (a.x == b.x)
{
return a.y < b.y;
}
return a.x < b.x;
}
void read()
{
FILE * f = fopen("infasuratoare.in", "r");
fscanf(f, "%d", &n);
for (int i = 1; i <= n; i++)
{
fscanf(f, "%lf %lf", &puncte[i].x, &puncte[i].y);
}
/* sortare puncte dupa x, apoi y*/
sort(puncte + 1, puncte + n + 1, how);
fclose(f);
}
int ecdreptei(point a, point b, point c)
{
if((c.x-a.x)*(a.y-b.y)-(a.x-b.x)*(c.y-a.y)<0) return true;
return false;
}
void infasuratoare()
{
st[++vf]=1; st[++vf]=2; used[2]=1; dir=1; urmator=3;
/* cat timp nu am ajuns de unde am plecat*/
while (used[1] == 0)
{
while (used[urmator] != 0)
{
if (urmator == n)
{
dir = -1;
}
urmator += dir;
}
while (vf >= 2 && ecdreptei(puncte[st[vf-1]], puncte[st[vf]], puncte[urmator]))
{
used[st[vf--]] = 0;
}
st[++vf] = urmator;
used[urmator] = 1;
}
}
void write()
{
FILE * g = fopen("infasuratoare.out", "w");
fprintf(g, "%d\n", vf - 1);
for (int i = 1; i < vf; i++)
{
fprintf(g, "%.6lf %.6lf\n", puncte[st[i]].x, puncte[st[i]].y);
}
fclose(g);
}
int main()
{
read();
infasuratoare();
write();
}