Pagini recente » Borderou de evaluare (job #2734575) | monopoly | Borderou de evaluare (job #2961649) | Cod sursa (job #880197)
Cod sursa(job #880197)
#include <fstream>
#include <iomanip>
#include <limits>
#include <algorithm>
#include <cmath>
using namespace std;
#define Point pair<double, double>
#define InFile "infasuratoare.in"
#define OutFile "infasuratoare.out"
#define NMax 120000
int P, H;
Point points[NMax];
Point hull[NMax];
inline double crossProduct(const Point &p0, const Point &p1, const Point &p2)
{
return (p1.first - p0.first) * (p2.second - p0.second) - (p1.second - p0.second) * (p2.first - p0.first);
}
inline bool minimumCompare(const Point &p1, const Point &p2)
{
return p1.first < p2.first || p1.first == p2.first && p1.second < p2.second;
}
inline bool angleCompare(const Point &p1, const Point &p2)
{
return crossProduct(points[0], p1, p2) > 0;
}
inline void clear(int p)
{
while (H >= 2 && crossProduct(hull[H - 2], hull[H - 1], points[p]) < 0)
{
--H;
}
}
void read()
{
ifstream fin(InFile);
fin >> P;
for (int p = 0; p < P; ++p)
{
fin >> points[p].first >> points[p].second;
}
fin.close();
}
void solve()
{
// Find minimum
swap(*min_element(points, points + P, minimumCompare), points[0]);
// Sort rest of points
sort(points + 1, points + P, angleCompare);
// Insert base elements in hull
hull[H++] = points[0];
hull[H++] = points[1];
// Compute convex hull
for (int p = 2; p < P; ++p)
{
clear(p);
hull[H++] = points[p];
}
}
void write()
{
ofstream fout(OutFile);
fout << H << '\n';
for (int h = 1; h < H; ++h)
{
fout << setprecision(12) << hull[h].first << ' ' << hull[h].second << '\n';
}
fout << setprecision(12) << hull[0].first << ' ' << hull[0].second << '\n';
fout.close();
}
int main()
{
read();
solve();
write();
}