Pagini recente » Cod sursa (job #1618859) | Cod sursa (job #563835) | Cod sursa (job #1646948) | Cod sursa (job #2269202) | Cod sursa (job #843771)
Cod sursa(job #843771)
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;
ifstream fi ("infasuratoare.in");
ofstream fo ("infasuratoare.out");
const int dim = 120005;
int N, I[dim];
struct punct { double x, y; } P[dim];
double ariedet (punct p1, punct p2, punct p3)
{
return (p1.x - p2.x) * (p3.y - p2.y) - (p3.x - p2.x) * (p1.y - p2.y);
}
int cmp (punct p2, punct p3)
{
punct p1 = P[0];
double d = ariedet (p1, p2, p3);
if (d == 0)
{
d = (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) - (p1.x-p3.x)*(p1.x-p3.x) - (p1.y-p3.y)*(p1.y-p3.y);
return d > 0;
}
return d < 0;
}
void cit ()
{
int i, best = 0;
fi >> N;
for (i = 0; i < N; i++)
{
fi >> P[i].x >> P[i].y;
if (P[i].x < P[best].x || (P[i].x == P[best].x && P[i].y < P[best].y))
best = i;
}
swap (P[0], P[best]);
sort (P+1, P+N, cmp);
for (i = 2; ariedet (P[0], P[1], P[i]) == 0; i++);
for (int j = 1; j <= (i>>1); j++) swap (P[j], P[i-j]);
}
void inf ()
{
I[++I[0]] = 0;
I[++I[0]] = 1;
for (int i = 2; i < N; i++)
{
while (I[0] > 2 && ariedet (P[I[I[0]-1]], P[I[I[0]]], P[i]) > 0)
I[0]--;
I[++I[0]] = i;
}
}
void afi ()
{
fo << I[0] << '\n';
for (int i = 1; i <= I[0]; i++)
fo << P[I[i]].x << ' ' << P[I[i]].y << '\n';
}
int main ()
{
cit ();
inf ();
afi ();
return 0;
}