Pagini recente » Cod sursa (job #1161856) | Cod sursa (job #549518) | Monitorul de evaluare | Cod sursa (job #2159748) | Cod sursa (job #407628)
Cod sursa(job #407628)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const int MAX_N = 120010;
#define x first
#define y second
#define punct pair<double, double>
int n;
punct a[MAX_N];
int s[MAX_N], viz[MAX_N];
int signum(punct a, punct b, punct c)
{
return 1 - ((a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y) <= 0);
}
int main()
{
int i, p,k;
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
for (i = 1; i <= n; ++i)
scanf("%f%f",&a[i].x,&a[i].y);
fclose(stdin);
sort(a + 1, a + n + 1);
k=1;
s[k] = 1;
for (i = 2, p = 1; i; i=i+ (p = (i == n) ? -p : p))
{
if (!viz[i])
{
while (k > 1 && signum(a[i], a[s[k]], a[s[k - 1]]))
viz[s[k--]] = 0;
viz[s[++k] = i] = 1;
}
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n",k-1);
for (i = 1; i < k; ++i)
printf("%.6f %.6f\n",a[s[i]].x,a[s[i]].y);
fclose(stdout);
return 0;
}