Pagini recente » Cod sursa (job #2120513) | Cod sursa (job #2050576) | Cod sursa (job #1527481) | Cod sursa (job #1869470) | Cod sursa (job #604783)
Cod sursa(job #604783)
#include <iostream>
#include <algorithm>
#define NMax 120005
#define Inf 2000000000
using namespace std;
typedef struct
{
double x, y;
}
Coord;
Coord P[NMax];
int N, Stack[NMax], K;
inline bool cmp (Coord A, Coord B)
{
if ((A.x-P[1].x)*(B.y-P[1].y)>(B.x-P[1].x)*(A.y-P[1].y))
{
return true;
}
return false;
}
void Read ()
{
freopen ("infasuratoare.in", "r", stdin);
scanf ("%d", &N);
double XMin=Inf, YMin=Inf;
int iMin=0;
for (int i=1; i<=N; ++i)
{
scanf ("%lf %lf", &P[i].x, &P[i].y);
if (P[i].x==XMin and P[i].y<YMin)
{
iMin=i;
YMin=P[i].y;
}
if (P[i].x<XMin)
{
iMin=i;
XMin=P[i].x;
YMin=P[i].y;
}
}
Coord Aux=P[1];
P[1]=P[iMin];
P[iMin]=Aux;
sort (P+2, P+N+1, cmp);
}
void Print ()
{
freopen ("infasuratoare.out", "w", stdout);
printf ("%d\n", K);
for (int i=1; i<=K; ++i)
{
printf ("%lf %lf\n", P[Stack[i]].x, P[Stack[i]].y);
}
}
inline float Sign (Coord A, Coord B, Coord C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
void ConvexHull ()
{
Stack[1]=1;
Stack[2]=2;
K=2;
int i=2;
while (i<N)
{
++i;
while (K>1 and Sign (P[Stack[K]], P[Stack[K-1]], P[i])>0)
{
--K;
}
Stack[++K]=i;
}
}
int main()
{
Read ();
ConvexHull ();
Print ();
return 0;
}