Pagini recente » Cod sursa (job #1569041) | Cod sursa (job #3208333) | Rating kokos vasile (kukurigu) | Cod sursa (job #970913) | Cod sursa (job #1536232)
#include <bits/stdc++.h>
#define point pair < double , double >
#define x first
#define y second
using namespace std;
const int Nmax = 120000 + 10;
const int eps = 1e-12;
int n , i;
point p[Nmax];
bool ok[Nmax];
vector < int > st;
int compare(double a , double b)
{
if (a + eps < b) return -1;
if (b + eps < a) return 1;
return 0;
}
int semn(point a , point b , point c)
{
///determinant
double sum = 0;
sum += a.x*b.y + b.x*c.y + a.y*c.x;
sum -= c.x*b.y + b.x*a.y + a.x*c.y;
return compare(sum , 0);
}
void cevaCorect()
{
int mod = 1 , crt = 3;
st.push_back(1); st.push_back(2); ok[2] = 1;
while (!ok[1])
{
while (ok[crt])
{
if (crt == n) mod = -1;
crt += mod;
}
while (st.size() > 1 && semn(p[st[st.size()-2]] , p[st[st.size()-1]] , p[crt]) == 1)
ok[st.back()] = 0, st.pop_back();
st.push_back(crt); ok[crt] = 1;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d", &n);
for (i = 1; i <= n; ++i)
scanf("%lf %lf", &p[i].x, &p[i].y);
sort(p + 1 , p + n + 1);
cevaCorect();
for (printf("%d\n", st.size()-1) ; st.size() > 1; st.pop_back())
printf("%f %f\n", p[st.back()].x , p[st.back()].y);
return 0;
}