Pagini recente » Cod sursa (job #2574968) | Cod sursa (job #616917) | Cod sursa (job #609129) | Cod sursa (job #1709295) | Cod sursa (job #544829)
Cod sursa(job #544829)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIM 120005
int N, O, S[DIM];
struct punct { double x, y; } P[DIM], T;
int cmp (punct a, punct b)
{
return a.y * b.x < a.x * b.y;
}
int determ3 (punct a, punct b, punct c)
{
return (b.x*c.y + a.x*b.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y) < 0;
}
void citire ()
{
scanf ("%d", &N);
for (int i = 0; i < N; i++)
{
scanf ("%lf%lf", &P[i].x, &P[i].y);
if (P[O].y > P[i].y)
O = i;
}
}
void sortare ()
{
punct aux = P[O]; P[O] = P[0]; P[0] = aux;
T = P[0];
for (int i = 0; i < N; i++)
P[i].x -= T.x, P[i].y -= T.y;
sort (P + 1, P + N, cmp);
}
void infasoara ()
{
S[++S[0]] = 0;
S[++S[0]] = 1;
for (int i = 2; i < N; i++)
{
while (determ3 (P[S[S[0] - 1]], P[S[S[0]]], P[i]))
S[0] --;
S[++S[0]] = i;
}
}
void afisare ()
{
printf ("%d\n", S[0]);
for (int i = 1; i <= S[0]; i++)
printf ("%lf %lf\n", P[S[i]].x + T.x, P[S[i]].y + T.y);
}
int main ()
{
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
citire ();
sortare ();
infasoara ();
afisare ();
return 0;
}