Pagini recente » Cod sursa (job #980271) | Cod sursa (job #875404) | Cod sursa (job #998142) | Statistici UAIC BOO (UAIC_Buruiana_Oprea_Ouatu) | Cod sursa (job #630075)
Cod sursa(job #630075)
#include <cstdio>
#include <algorithm>
#define NMax 120005
#define x first
#define y second
using namespace std;
pair <double, double> P[NMax];
int N, M, K, S[NMax];
void Read ()
{
freopen ("infasuratoare.in", "r", stdin);
scanf ("%d", &N);
M=1;
for (int i=1; i<=N; ++i)
{
scanf ("%lf %lf", &P[i].x, &P[i].y);
if (P[i].x==P[M].x)
{
if (P[i].y<P[M].y)
{
M=i;
}
}
if (P[i].x<P[M].x)
{
M=i;
}
}
}
void Print ()
{
freopen ("infasuratoare.out.out", "w", stdout);
printf ("%d\n", K);
for (int i=1; i<=K; ++i)
{
printf ("%lf %lf\n", P[S[i]].x, P[S[i]].y);
}
}
inline bool Compare (pair <double, double> A, pair <double, double> B)
{
if ((A.x-P[1].x)*(B.y-P[1].y)>(A.y-P[1].y)*(B.x-P[1].x))
{
return true;
}
return false;
}
inline double Angle (pair <double, double> A, pair <double, double> B, pair <double, double> C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-A.y*B.x-A.x*C.y;
}
inline void Push (int i)
{
S[++K]=i;
}
inline void Pop ()
{
S[K--]=0;
}
void ConvexHull ()
{
swap (P[M], P[1]);
sort (P+2, P+N+1, Compare);
Push (1);
Push (2);
for (int i=3; i<=N; ++i)
{
while (K>1 and Angle (P[S[K-2]], P[S[K-1]], P[i])<=0)
{
Pop ();
}
Push (i);
}
}
int main()
{
Read ();
ConvexHull ();
Print ();
return 0;
}