Pagini recente » Cod sursa (job #169555) | Cod sursa (job #625526) | Cod sursa (job #3180009) | Cod sursa (job #824573) | Cod sursa (job #2531532)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair < long double, long double > Point;
const int NMAX = 12e4 + 5;
int N;
Point A[NMAX];
int Stack[NMAX], K;
bool Sel[NMAX];
static inline void Read ()
{
f.tie(NULL);
f >> N;
for(int i = 1; i <= N; ++i)
f >> A[i].first >> A[i].second;
sort(A + 1, A + N + 1);
return;
}
static inline long double Det3 (Point A, Point B, Point C)
{
return (long double)(A.first * B.second + B.first * C.second + C.first * A.second) - (long double)(B.second * C.first + C.second * A.first + A.second * B.first);
}
static inline void Convex_Hull ()
{
Sel[2] = 1;
Stack[++K] = 1;
Stack[++K] = 2;
for(int i = 3; i <= N; ++i)
{
while(K > 1 && Det3(A[Stack[K - 1]], A[Stack[K]], A[i]) >= 0)
{
Sel[Stack[K]] = 0;
--K;
}
Sel[i] = 1;
Stack[++K] = i;
}
for(int i = N; i >= 1; --i)
if(!Sel[i])
{
while(K > 1 && Det3(A[Stack[K - 1]], A[Stack[K]], A[i]) >= 0)
{
Sel[Stack[K]] = 0;
--K;
}
Sel[i] = 1;
Stack[++K] = i;
}
return;
}
static inline void Write ()
{
g << (K - 1) << '\n';
g << setprecision(6) << fixed;
for(int i = 1; i < K; ++i)
g << A[Stack[i]].first << ' ' << A[Stack[i]].second << '\n';
return;
}
int main()
{
Read();
Convex_Hull();
Write();
return 0;
}