Pagini recente » Cod sursa (job #2236786) | Cod sursa (job #303967) | Cod sursa (job #1332664) | Cod sursa (job #2344898) | Cod sursa (job #1687399)
#include <bits/stdc++.h>
#define point pair < double , double >
#define x first
#define y second
#define eps 1e-12
using namespace std;
const int nmax = 1 << 17;
int n , i;
bool in[nmax];
point a[nmax];
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)
{
double sum = 0;
sum += a.x * b.y + b.x * c.y + a.y * c.x;
sum -= b.y * c.x + b.x * a.y + a.x * c.y;
return compare(sum , 0);
}
void convexhull()
{
int act = 3, mode = 1;
vector < int > st;
in[2] = 1;
st.push_back(1); st.push_back(2);
while (!in[1])
{
while (in[act])
{
if (act == n) mode *= -1;
act += mode;
}
while (st.size() > 1 && semn(a[st[st.size()-2]] , a[st[st.size()-1]] , a[act]) == 1)
in[st.back()] = 0, st.pop_back();
st.push_back(act); in[act] = 1;
}
st.pop_back();
for (printf("%d\n", (int)st.size()); st.size(); st.pop_back())
printf("%f %f\n", a[st.back()].x , a[st.back()].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d", &n);
for (i = 1; i <= n; ++i)
scanf("%lf %lf", &a[i].x, &a[i].y);
sort(a + 1 , a + n + 1);
convexhull();
return 0;
}