Pagini recente » Cod sursa (job #286014) | Cod sursa (job #2731041) | Cod sursa (job #865994) | Cod sursa (job #21306) | Cod sursa (job #969228)
Cod sursa(job #969228)
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
typedef std::pair<double,double> Point;
typedef std::vector<Point> Polygon;
const int MAX_SIZE(120001);
Polygon Hull;
std::vector<Point> Points;
int Stack [MAX_SIZE];
bool Mark [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 void Andrew (void)
{
std::sort(Points.begin(),Points.end());
const int END(Points.size() - 1);
Stack[0] = 0;
//Mark[0] = true;
int top(0);
for (int index(1), sign(1) ; index >= 0 ; index += (sign = (index == END ? -sign : sign)))
{
if (Mark[index])
continue;
while (top >= 1 && Determinant(Points[Stack[top - 1]],Points[Stack[top]],Points[index]) > 0)
Mark[Stack[top--]] = false;
Stack[++top] = index;
Mark[index] = true;
}
--top;
while (top >= 0)
Hull.push_back(Points[Stack[top--]]);
}
int main (void)
{
Read();
Andrew();
Print();
return 0;
}