Pagini recente » Cod sursa (job #710804) | Cod sursa (job #306377) | Cod sursa (job #1878854) | Cod sursa (job #92432) | Cod sursa (job #1843538)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct vec2
{
double x, y;
vec2(double xx, double yy) : x(xx), y(yy) {}
vec2(double a = 0) : x(a), y(a) {}
inline double len() const { return sqrt(x*x + y*y); }
inline vec2& normalize() {
double l = len();
x /= l; y /= l;
}
inline double dot(const vec2& a) const { return x * a.x + y * a.y; }
inline double crossZ(const vec2& a) const { return x * a.y - y * a.x; }
inline vec2 operator+(const vec2& a) const { return vec2(x + a.x, y + a.y); }
inline vec2 operator-(const vec2& a) const { return vec2(x - a.x, y - a.y); }
} v[120001];
inline double crossZ(const vec2& a, const vec2& b) { return a.crossZ(b); }
bool cmp(const vec2& a, const vec2& b)
{
return crossZ(a - v[0], b - v[0]) > 0;
}
int n;
int h[120001], lh;
int main()
{
vec2 vaux;
int i, j;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(i = 0; i < n; i++)
{
scanf("%lf%lf", &v[i].x, &v[i].y);
if(v[i].x < v[0].x || (v[i].x == v[0].x && v[i].y < v[0].y))
{
vaux = v[0];
v[0] = v[i];
v[i] = vaux;
}
}
sort(v + 1, v + n, cmp);
h[0] = 0;
h[1] = 1;
lh = 2;
for(i = 2; i < n; i++)
{
while(crossZ(v[i] - v[h[lh - 2]], v[h[lh - 1]]- v[h[lh - 2]]) > 0)
lh--;
h[lh++] = i;
}
printf("%d\n", lh);
for(i = 0; i < lh; i++)
{
printf("%lf %lf\n", v[h[i]].x, v[h[i]].y);
}
return 0;
}