Pagini recente » Cod sursa (job #731799) | Cod sursa (job #2678887) | Cod sursa (job #2820494) | Cod sursa (job #2738570) | Cod sursa (job #933623)
Cod sursa(job #933623)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
#define Nmax 120010
#define PD pair<double, double>
#define mp make_pair
#define x first
#define y second
PD V[Nmax], Stack[Nmax], Convex[Nmax];
int N, K;
double Det(PD A, PD B, PD C)
{
return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}
void Add_Points()
{
int StackSize = 0;
Stack[StackSize ++] = V[1];
Stack[StackSize ++] = V[2];
for(int i = 3; i <= N; ++ i)
{
while(StackSize >= 2 && Det(Stack[StackSize - 2], Stack[StackSize - 1], V[i]) < 0) StackSize --;
Stack[StackSize ++] = V[i];
}
for(int i = 0; i < StackSize - 1; ++ i) Convex[++ K] = Stack[i];
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int i;
scanf("%i", &N);
for(i = 1; i <= N; ++ i) scanf("%lf %lf", &V[i].x, &V[i].y);
sort(V + 1, V + N + 1);
Add_Points();
reverse(V + 1, V + N + 1);
Add_Points();
printf("%i\n", K);
for(i = 1; i <= K; ++ i) printf("%lf %lf\n", Convex[i].x, Convex[i].y);
return 0;
}