Pagini recente » Cod sursa (job #124676) | Cod sursa (job #2972917) | Cod sursa (job #1197618)
#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) {};
double x;
double y;
};
Point smallestY;
vector<Point> points;
vector<Point> convexHull;
stack<Point> hull;
/**
* Se bazeaza pe calculul ariei cu determinantul.
*/
int isClockWise(Point &a, Point &b, Point &c)
{
double area = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
if (area < 0)
return -1; // Nu este clockwise
else if (area > 0)
return 1;
else
return 0; // Sunt coliniare
}
bool yCmp(Point a, Point b)
{
if (fabs(a.y - b.y) < EPS)
return false;
else if (a.y < b.y)
return true;
else
return false;
}
bool slopeCmp(Point a, Point b)
{
double angle1 = atan2(a.y - smallestY.y, a.x - smallestY.x) * 180 / M_PI;
double angle2 = atan2(b.y - smallestY.y, b.x - smallestY.x) * 180 / M_PI;
if (angle1 < 0)
angle1 = 360.0 + angle1;
if (angle2 < 0)
angle2 = 360.0 + angle2;
if (fabs(angle1 - angle2) < EPS)
return false;
else if (angle1 < angle2)
return true;
else
return false;
}
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;
fin >> N;
for (int i = 0; i < N; ++i) {
double x, y;
fin >> x >> y;
points.push_back(Point(x, y));
}
sort(points.begin(), points.end(), yCmp);
smallestY = points[0];
sort(points.begin() + 1, points.end(), slopeCmp);
hull.push(points[0]);
hull.push(points[1]);
for (int i = 2; i < N; ++i) {
Point top = hull.top();
hull.pop();
while (isClockWise(hull.top(), top, points[i]) <= 0) {
top = hull.top();
hull.pop();
}
hull.push(top);
hull.push(points[i]);
}
while (!hull.empty()) {
Point p = hull.top();
convexHull.push_back(p);
hull.pop();
}
fout << convexHull.size() << endl;
for (int i = convexHull.size() - 1; i >= 0; --i)
fout << convexHull[i].x << " " << convexHull[i].y << endl;
fin.close();
fout.close();
return 0;
}