Pagini recente » Cod sursa (job #454306) | Cod sursa (job #991179) | Cod sursa (job #2340748) | Cod sursa (job #2385938) | Cod sursa (job #969150)
Cod sursa(job #969150)
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
typedef std::pair<double,double> Point;
typedef std::vector<Point> Polygon;
const int MAX_SIZE(120001);
const double GUARD(0.00000001);
Polygon Hull;
std::vector<Point> Points;
Point Stack [MAX_SIZE];
inline void Read (void)
{
std::freopen("infasuratoare.in","r",stdin);
double x, y;
int n;
std::scanf("%d",&n);
for (int counter(0) ; counter < n ; ++counter)
{
std::scanf("%lf %lf",&x,&y);
Points.push_back(std::make_pair(x,y));
}
std::fclose(stdin);
}
inline void Print (void)
{
std::freopen("infasuratoare.out","w",stdout);
std::printf("%lu\n",Hull.size());
for (int index(0), end(Hull.size()) ; index < end ; ++index)
std::printf("%.9lf %.9lf\n",Hull[index].first,Hull[index].second);
std::fclose(stdout);
}
inline double Determinant (Point &a, Point &b, Point &c)
{
return a.first * b.second - a.second * b.first + b.first * c.second - b.second * c.first + c.first * a.second - c.second * a.first;
}
inline double Area (Polygon &p)
{
const int END(p.size());
double result(0);
p.push_back(p.front());
for (int index(0) ; index < END ; ++index)
result += p[index].first * p[index + 1].second - p[index].second * p[index + 1].first;
p.pop_back();
return result / 2;
}
inline bool InPolygon (Polygon &a, Point &b)
{
const int END(a.size() - 1);
int index;
double result(0), area(Area(a));
for (index = 0 ; index < END ; ++index)
result += std::abs(Determinant(a[index],a[index + 1],b));
result /= 2;
return (result > area - GUARD && result < area + GUARD);
}
inline void Graham (void)
{
const int END(Points.size());
int index;
int sx(0), sy(0), bx(0), by(0);
for (index = 0 ; index < END ; ++index)
{
if (Points[index].first < sx)
sx = index;
if (Points[index].first > bx)
bx = index;
if (Points[index].second < sy)
sy = index;
if (Points[index].second > by)
by = index;
if (Points[index] < Points[0])
std::swap(Points[0],Points[index]);
}
Polygon q;
if (std::find(q.begin(),q.end(),Points[sx]) == q.end())
q.push_back(Points[sx]);
if (std::find(q.begin(),q.end(),Points[sy]) == q.end())
q.push_back(Points[sy]);
if (std::find(q.begin(),q.end(),Points[bx]) == q.end())
q.push_back(Points[bx]);
if (std::find(q.begin(),q.end(),Points[by]) == q.end())
q.push_back(Points[by]);
if (q.size() >= 3)
{
Polygon tmp;
for (index = 0 ; index < END ; ++index)
if (std::find(q.begin(),q.end(),Points[index]) == q.end())
{
if (!InPolygon(q,Points[index]))
tmp.push_back(Points[index]);
}
else
tmp.push_back(Points[index]);
Points = tmp;
}
std::sort(Points.begin() + 1,Points.end(), [ ] (Point a, Point b) -> bool {return Determinant(Points[0],a,b) < 0;});
Stack[0] = Points[0];
Stack[1] = Points[1];
int top(1);
for (index = 2 ; index < END ; ++index)
{
while (top >= 1 && Determinant(Stack[top - 1],Stack[top],Points[index]) > 0)
--top;
Stack[++top] = Points[index];
}
while (top >= 0)
{
Hull.push_back(Stack[top]);
--top;
}
}
int main (void)
{
Read();
Graham();
Print();
return 0;
}