Pagini recente » Cod sursa (job #1017465) | Cod sursa (job #2520173) | Cod sursa (job #1992989) | Cod sursa (job #644897) | Cod sursa (job #3353776)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
class Point{
public:
double x, y;
Point(double x, double y): x(x), y(y) {}
friend istream& operator>>(istream& is, Point& p) {
is >> p.x >> p.y;
return is;
}
friend ostream& operator<<(ostream& os, const Point& p) {
os << fixed << setprecision(6) << p.x << ' ' << p.y;
return os;
}
bool operator==(const Point& p1) const {
return p1.x == x && p1.y == y;
}
};
int n;
vector<Point> points;
double dist2(const Point& a, const Point& b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return dx * dx + dy * dy;
}
/*
delta > 0 => left
delta < 0 => right
delta = 0 => colinear
*/
double delta(Point A, Point B, Point C) {
double xa = A.x, ya = A.y;
double xb = B.x, yb = B.y;
double xc = C.x, yc = C.y;
return xa * (yb - yc) + xb * (yc - ya) + xc * (ya - yb);
}
void read() {
fin >> n;
for(int i = 0; i < n; i++) {
double x, y;
fin >> x >> y;
points.push_back(Point(x, y));
}
}
vector<Point> graham_scan() {
// start point
int idx = 0;
for(int i = 1; i < n; i++) {
if(points[i].y < points[idx].y || (points[i].y == points[idx].y && points[i].x < points[idx].x))
idx = i;
}
swap(points[0], points[idx]);
Point start = points[0];
// sortare dupa unghi
sort(points.begin() + 1, points.end(),
[&](const Point& a, const Point& b) {
double cross = delta(start, a, b);
// start, a, b sunt cooliniare
if(cross == 0)
return dist2(start, a) < dist2(start, b);
return cross > 0;
}
);
// scan
stack<Point> s;
s.push(points[0]);
s.push(points[1]);
for(int i = 2; i < n; i++) {
while(s.size() >= 2) {
Point top = s.top();
s.pop();
Point next = s.top();
// left turn
if(delta(next, top, points[i]) > 0) {
s.push(top);
break;
}
}
s.push(points[i]);
}
// get the hull
vector<Point> hull;
while(!s.empty()) {
hull.push_back(s.top());
s.pop();
}
reverse(hull.begin(), hull.end());
return hull;
}
int main() {
read();
auto hull = graham_scan();
fout << hull.size() << "\n";
for(auto &x : hull) {
fout << x << '\n';
}
return 0;
}