Pagini recente » Cod sursa (job #785452) | Cod sursa (job #690085) | Cod sursa (job #570703) | Cod sursa (job #717501) | Cod sursa (job #578357)
Cod sursa(job #578357)
#include <fstream>
#include <utility>
#include <algorithm>
#define x first
#define y second
using namespace std;
inline double semn(pair <double, double> &A, pair<double, double> &B, pair<double, double> &C)
{
return A.x * B.y + B.x * C.y + A.y * C.x - C.x * B.y - B.x * A.y - A.x * C.y;
}
int N;
pair<double, double> P[120100];
int S[120100], K, In[120100];
int main()
{
freopen ("infasuratoare.in", "r" ,stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf("%d\n", &N);
int i, t = 1;
for(i = 1; i <= N; i++)
scanf("%lf %lf", &P[i].x, &P[i].y);
sort( P + 1, P + 1 + N );
S[1] = 1; S[2] = 2; K = 2;
In[1] = In[2] = 1;
i = 2;
while(i > 1)
{
if(t > 0 && i < N)
i += t;
else {
t = -1;
while(In[i] && i > 1)
i += t;
if(i == 1)
break;
}
while(K > 1 && semn(P[S[K]], P[S[K - 1]], P[i]) > 0)
In[S[K]] = 0, --K;
S[++K] = i;
In[i] = 1;
}
printf("%d\n", K);
for(i = 1; i <= K; i++)
printf("%lf %lf\n", P[S[i]].x, P[S[i]].y);
return 0;
}