Pagini recente » Cod sursa (job #1181449) | Cod sursa (job #2968044) | Cod sursa (job #496761) | Cod sursa (job #1250845) | Cod sursa (job #1615645)
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
using namespace std;
int n;
struct vec2
{
vec2(double a = 0) : x(a), y(a) {}
vec2(double xx, double yy) : x(xx), y(yy) {}
double x, y;
};
struct Point
{
vec2 pos;
double angle;
};
inline double getDistance(const vec2& a, const vec2& b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
inline double getDistanceSq(const vec2& a, const vec2& b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
inline double getAngle(const vec2& a)
{
return atan2(a.y, a.x);
}
inline double getLength(const vec2& a)
{
return sqrt(a.x * a.x + a.y * a.y);
}
inline vec2 getNorm(const vec2& a)
{
double len = getLength(a);
return vec2(a.x / len, a.y / len);
}
int pointComp(const void* aa, const void* bb)
{
double d = ((Point*)aa)->angle - ((Point*)bb)->angle;
if(d < 0)
return -1;
if(d > 0)
return 1;
return 0;
}
int mod(int pos)
{
if(pos >= n)
return pos - n;
return pos;
}
double crossZ(const vec2& a, const vec2& b)
{
return a.x * b.y - a.y * b.x;
}
int getSide(const vec2& a, const vec2& b, const vec2& m)
{
vec2 amv(m.x - a.x, m.y - a.y);
vec2 mbv(b.x - m.x, b.y - m.y);
double res = crossZ(amv, mbv);
if(res < 0)
return -1;
return 1;
}
int main()
{
bool ok;
double lmax = 0, l;
int i, j, lres = 0, llmax = 0;
Point* v;
vec2* res, center(0, 0);
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> n;
v = new Point[n];
res = new vec2[n];
for(i = 0; i < n; i++)
{
f >> v[i].pos.x >> v[i].pos.y;
center.x += v[i].pos.x;
center.y += v[i].pos.y;
//v[i].angle = getAngle(v[i].pos);
}
center.x /= n;
center.y /= n;
for(i = 0; i < n; i++)
{
v[i].pos.x -= center.x;
v[i].pos.y -= center.y;
v[i].angle = getAngle(v[i].pos);
}
qsort(v, n, sizeof(Point), pointComp);
lmax = getLength(v[i].pos);
for(i = 1; i < n; i++)
{
l = getLength(v[i].pos);
if(l > lmax)
{
lmax = l;
llmax = i;
}
}
res[0] = v[llmax].pos;
lres = 1;
for(i = llmax + 1; i < llmax + n; i++)
{
ok = true;
for(j = lres - 2; j >= 0; j--)
{
if(getSide(res[j], v[mod(i)].pos, res[j + 1]) == 1)
{
break;
}
ok = false;
}
if(ok)
{
res[lres++] = v[mod(i)].pos;
}
else
{
lres = j + 2;
res[lres++] = v[mod(i)].pos;
}
}
lres--;
g << lres << '\n';
for(i = 0; i < lres; i++)
{
g << res[i].x + center.x << ' ' << res[i].y + center.y << '\n';
}
f.close();
g.close();
return 0;
}