Pagini recente » Cod sursa (job #272754) | Cod sursa (job #3206895) | Cod sursa (job #2350597) | Cod sursa (job #2548407) | Cod sursa (job #2350711)
#include <bits/stdc++.h>
#define maxN 120002
#define eps 0.000000001
using namespace std;
FILE *fin = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);
/* ------------------------------------------------------- */
int n;
struct Point
{
double x, y;
bool operator < (const Point &ot) const
{
if (fabs(x - ot.x) < eps)
return y < ot.y;
return x < ot.x;
}
} v[maxN];
struct PolarPoint
{
double r, alpha;
bool operator < (const PolarPoint &ot) const
{
if (fabs(alpha - ot.alpha) < eps)
return r > ot.r;
return alpha > ot.alpha;
}
} V[maxN];
/* ------------------------------------------------------- */
double CrossProd(Point O, Point A, Point B)
{
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
Point PPtoP(PolarPoint p)
{
double r = p.r, alpha = p.alpha;
return {r * cos(alpha), r * sin(alpha)};
}
PolarPoint PtoPP(Point p)
{
double x = p.x, y = p.y;
double r = sqrt(x * x + y * y),
alpha = atan2(y, x);
//printf("%Lf %Lf %Lf %Lf\n", (long double)PPtoP({r, alpha}).x, (long double)PPtoP({r, alpha}).y, (long double)x, (long double)y);
return {r, alpha};
}
bool vis[maxN];
int st[2][maxN], head[2];
void ConvHull()
{
memset(vis, 0, sizeof(vis));
st[0][1] = 1;
st[0][2] = 2;
head[0] = 2;
vis[2] = true;
for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p)))
{
if (vis[i]) continue;
while (head[0] >= 2 && CrossProd(v[st[0][head[0] - 1]], v[st[0][head[0]]], v[i]) > eps)
vis[st[0][head[0] --]] = false;
st[0][++ head[0]] = i;
vis[i] = true;
}
-- head[0];
}
void Convhull()
{
sort(V + 2, V + n + 1);
head[1] = 2;
st[1][1] = 1;
st[1][2] = 2;
for (int i = 3; i <= n; ++ i)
{
while (head[1] > 1 && CrossProd(PPtoP(V[st[1][head[1] - 1]]), PPtoP(V[st[1][head[1]]]), PPtoP(V[i])) > -eps)
-- head[1];
st[1][++ head[1]] = i;
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
scanf("%lf %lf", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1);
V[1] = PtoPP({0, 0});
for (int i = 2; i <= n; ++ i)
V[i] = PtoPP({v[i].x - v[1].x, v[i].y - v[1].y});
ConvHull();
Convhull();
/*if (head[0] != head[1])
exit(0);*/
int t = 0;
printf("%d\n", head[t]);
for (int i = 1; i <= head[t]; ++ i)
printf("%Lf %Lf\n", (long double)v[st[0][i]].x, (long double)v[st[0][i]].y);
return 0;
}