Pagini recente » Cod sursa (job #1910045) | Cod sursa (job #2384147) | Cod sursa (job #2693134) | Cod sursa (job #1304930) | Cod sursa (job #2108503)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define X first
#define Y second
#define eps 1e-12
using namespace std;
typedef pair<double, double> point;
vector<point> points;
vector<point> sol;
void read() {
ifstream in("infasuratoare.in");
int n;
double x, y;
int left = 0;
for (in >> n; n; --n) {
in >> x >> y;
points.push_back(make_pair(x, y));
if (x - points[left].X <= -eps || (fabs(x - points[left].X) < eps && y - points[left].Y <= -eps))
left = points.size() - 1;
}
swap(points[0], points[left]);
in.close();
}
double crossProduct(const point& p, const point& q, const point& r) {
return (q.X - p.X) * (r.Y - p.Y) - (r.X - p.X) * (q.Y - p.Y);
}
double dist(const point& p, const point& q) {
return (q.X - p.X) * (q.X - p.X) + (q.Y - p.Y) * (q.Y - p.Y);
}
bool compare(const point& p1, const point &p2) {
double orientation = crossProduct(points[0], p1, p2);
if (orientation >= eps || (fabs(orientation) < eps && dist(points[0], p1) < dist(points[0], p2)))
return true;
return false;
}
int main() {
read();
sort(points.begin() + 1, points.end(), compare);
for (const point &p : points) {
while (sol.size() >= 2 && crossProduct(sol[sol.size() - 2], sol.back(), p) < eps)
sol.pop_back();
sol.push_back(p);
}
ofstream out("infasuratoare.out");
out << sol.size() << "\n";
out << fixed << setprecision(6);
for (const point &p : sol)
out << p.X << " " << p.Y << "\n";
out.close();
return 0;
}