Pagini recente » Cod sursa (job #2596323) | Cod sursa (job #1889361) | Cod sursa (job #1317260) | Cod sursa (job #1614186) | Cod sursa (job #2878955)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cassert>
#include <algorithm>
#include <set>
#include <iomanip>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <map>
#include <random>
#include <chrono>
#include <cstdio>
using namespace std;
typedef double ld;
class Vector {
public:
ld x, y;
};
Vector operator + (Vector a, Vector b) { return { a.x + b.x, a.y + b.y }; }
Vector operator - (Vector a, Vector b) { return { a.x - b.x, a.y - b.y }; }
Vector operator * (Vector a, ld b) { return { a.x * b, a.y * b }; }
Vector operator / (Vector a, ld b) { return { a.x / b, a.y / b }; }
Vector operator * (ld b, Vector a) { return { a.x * b, a.y * b }; }
ld dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
ld cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
ld get_norm(Vector a) { return sqrt(a.x * a.x + a.y * a.y); }
Vector normalize(Vector a) { return a / get_norm(a); }
ld getArea(Vector a, Vector b) { return (a.x + b.x) * (a.y - b.y); }
ld getArea(Vector a, Vector b, Vector c) { return getArea(a, b) + getArea(b, c) + getArea(c, a); }
Vector spec;
bool operator < (Vector p1, Vector p2) {
return getArea(spec, p1, p2) < 0;
}
class Hulk {
private:
public:
vector<Vector> Hulkize(vector<Vector> points) {
assert(!points.empty());
int n = (int)points.size();
for (int i = 1; i < n; i++) {
if (points[i].x < points[0].x) {
swap(points[i], points[0]);
}
else {
if (points[i].x == points[0].x && points[i].y < points[0].y) {
swap(points[i], points[0]);
}
}
}
spec = points[0];
sort(points.begin() + 1, points.end());
points.push_back(points[0]);
vector<Vector> sol;
for (auto& p : points) {
while ((int)sol.size() >= 2 && getArea(sol[(int)sol.size() - 2], sol[(int)sol.size() - 1], p) > 0) {
sol.pop_back();
}
sol.push_back(p);
}
return sol;
}
};
signed main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
cin >> n;
vector<Vector> v(n);
for (auto& p : v) {
cin >> p.x >> p.y;
}
Hulk hulk;
v = hulk.Hulkize(v);
v.pop_back();
cout << (int)v.size() << "\n";
for (auto& p : v) {
cout << fixed << setprecision(6) << p.x << " " << p.y << "\n";
}
}