Pagini recente » Cod sursa (job #2972917) | Cod sursa (job #1197618) | Cod sursa (job #3292911) | Cod sursa (job #3285878) | Cod sursa (job #1197622)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
#define NMAX 120005
#define EPS 1.000e-12
using namespace std;
struct Point {
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {};
bool operator<( const Point &other ) const
{
return x < other.x || y < other.y;
}
double x;
double y;
};
Point points[NMAX];
Point hull[NMAX];
/**
* Se bazeaza pe calculul ariei cu determinantul.
*/
double clockWiseDet(Point &a, Point &b, Point &c)
{
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
bool clockWiseCmp(Point a, Point b)
{
return clockWiseDet(points[0], a, b) < 0;
}
int main()
{
ifstream fin;
ofstream fout;
fin.open("infasuratoare.in");
fout.open("infasuratoare.out");
fout.precision(6);
fout.setf(std::ios::fixed, std::ios::floatfield);
int N;
int head;
fin >> N;
for (int i = 0; i < N; ++i) {
double x, y;
fin >> x >> y;
points[i] = Point(x, y);
}
int pos = 0;
for (int i = 1; i < N; ++i)
if (points[i] < points[pos])
pos = i;
swap(points[0], points[pos]);
sort(points + 1, points + N, clockWiseCmp);
hull[0] = points[0];
hull[1] = points[1];
head = 2;
for (int i = 2; i < N; ++i) {
while (head >= 2 &&
clockWiseDet(hull[head - 2], hull[head - 1], points[i]) > 0) {
--head;
}
hull[head++] = points[i];
}
fout << head << endl;
for (int i = head - 1; i >= 0; --i)
fout << hull[i].x << " " << hull[i].y << endl;
fin.close();
fout.close();
return 0;
}