Pagini recente » Cod sursa (job #2609027) | Cod sursa (job #1671261) | Cod sursa (job #2765315) | Cod sursa (job #47720) | Cod sursa (job #1226592)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
namespace math
{
static const double eps = 1.e-12;
static const double inf = 1.e9;
template<class T>
class POINT
{
private:
T x, y;
public:
POINT() : x(0), y(0) {};
POINT(T _x, T _y) : x(_x), y(_y) {};
POINT(const POINT& other) : x(other.x), y(other.y) {};
T getx() const
{
return x;
};
T gety() const
{
return y;
};
void setx(T _x)
{
x = _x;
};
void sety(T _y)
{
y = _y;
};
double distance(const POINT& other) const
{
return sqrt((x - other.x)*(x - other.x) + (y - other.y)*(y - other.y));
}
POINT middle(const POINT& other) const
{
return POINT((x + other.x) / 2, (y + other.y) / 2);
}
bool operator == (const POINT& other) const
{
return (fabs(x - other.x) < eps && fabs(y - other.y) < eps);
}
double cp(const POINT& b, const POINT& c) const
{
return (b.x - x) * (c.y - b.y) - (b.y - y) * (c.x - b.x);
}
int ccw(const POINT& b, const POINT& c) const
{
if(cp(b,c) < 0)
return -1;
if(cp(b,c) > 0)
return 1;
return 0;
}
};
}
using namespace math;
vector< POINT<double> > p;
int st[120005];
int top;
bool cmp(const POINT<double>& a,const POINT<double>& b)
{
if (p[0].ccw(a,b) > 0)
return true;
return false;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
double tx,ty;
int n,i;
scanf("%d",&n);
scanf("%lf%lf",&tx,&ty);
p.push_back(POINT<double>(tx,ty));
for(i=1;i<n;++i)
{
scanf("%lf%lf",&(tx),&(ty));
p.push_back(POINT<double>(tx,ty));
if( ((fabs(p[i].gety() - p[0].gety()) < eps) && p[i].getx() - p[0].getx() <= -eps) || ((p[i].gety() - p[0].gety()) <= -eps) )
swap(p[0],p[i]);
}
sort(p.begin()+1,p.end(),cmp);
p.push_back(*(p.begin()));
st[0] = 0;
st[1] = 1;
top = 1;
i = 2;
while(i <= n)
{
if(p[st[top-1]].ccw(p[st[top]],p[i]) > 0)
{
st[++top] = i;
++i;
}
else
--top;
}
printf("%d\n",top);
for(i=0;i<top;++i)
{
printf("%lf %lf\n",p[st[i]].getx(),p[st[i]].gety());
}
return 0;
}