Pagini recente » Cod sursa (job #1708956) | Cod sursa (job #3154368) | Cod sursa (job #2470237) | Cod sursa (job #2913666) | Cod sursa (job #3268825)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#define pdd pair<double,double>
#define x first
#define y second
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
const int NMAX = 120001;
pdd refPoint;
pdd operator- (pdd p1, pdd p2)
{
return make_pair (p1.x - p2.x, p1.y - p2.y);
}
ostream& operator<< (ostream& os, pdd p1)
{
os << p1.x << ' ' << p1.y << '\n';
return os;
}
int main()
{
int N;
f >> N;
vector<pdd> points (N + 1);
double maxCoordX = - 2e9;
int indMaxP = 0;
for (int i = 1; i <= N; i++)
{
f >> points[i].x >> points[i].y;
if (points[i].x > maxCoordX)
{
maxCoordX = points[i].x;
indMaxP = i;
}
else if (points[i].x == maxCoordX)
{
if (points[i].y < points[indMaxP].y)
{
indMaxP = i;
}
}
}
refPoint = points[indMaxP];
function<double (pdd, pdd) > dist = [] (pdd p1, pdd p2) -> double
{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
};
///returns the area of the parallelogram p1p2 + p1p3
auto computeAngle = [] (pdd p1, pdd p2, pdd p3) -> double
{
pdd p2t = p2 - p1;
pdd p3t = p3 - p1;
return (p2t.x * p3t.y - p3t.x * p2t.y);
};
sort (points.begin() + 1, points.end(), [&] (pdd p1, pdd p2) -> bool
{
double angle = computeAngle (refPoint, p1, p2);
return angle == 0 ? dist (p1, refPoint) < dist (p2, refPoint) : angle < 0;
});
vector<pdd> convexHull;
convexHull.pb (refPoint);
for (int i = 2; i <= N; i++)
{
while (convexHull.size() > 1 &&
computeAngle (convexHull.back(), * (convexHull.rbegin() + 1), points[i]) < 0)
{
convexHull.pop_back();
}
convexHull.pb (points[i]);
}
g << convexHull.size() << '\n';
refPoint = mp (0, 0);
sort (convexHull.begin(), convexHull.end(), [&] (pdd p1, pdd p2) -> bool
{
double angle = computeAngle (refPoint, p1, p2);
return angle == 0 ? dist (p1, refPoint) < dist (p2, refPoint) : angle > 0;
});
for (const auto &p : convexHull)
{
g << fixed << setprecision (12) << p;
}
return 0;
}