Pagini recente » Cod sursa (job #2709928) | Cod sursa (job #1732812) | Cod sursa (job #2202285) | Cod sursa (job #845525) | Cod sursa (job #2857863)
#include <bits/stdc++.h>
#define double long double
using namespace std;
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#endif
struct Point {
double x,y;
bool operator < (const Point other) const {
if (y != other.y) {
return y < other.y;
}
return x < other.x;
}
Point operator - (const Point other) const {
return Point{x - other.x , y - other.y};
}
};
double dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
bool rightTurn(Point a, Point b, Point c) {
return dot(b , a) > dot(c , b);
}
vector<Point> pt;
int n,i;
double x,y;
vector<Point> res;
Point lowLeft;
vector<Point> convexHull() {
lowLeft = pt[1];
for (i = 2; i <= n; i++) {
if (pt[i] < lowLeft) {
lowLeft = pt[i];
}
}
sort(pt.begin() + 1, pt.end() , [&](Point a, Point b) {
///we move everyone down by this low left guy, then sort this increasing by it's angle.
///this is also cool cause this makes the origin(lowLeft the first one)
return dot(a , lowLeft) < dot(b , lowLeft);
});
for (i = 1; i <= n; i++) {
while(res.size() >= 2 && rightTurn(res[(int)res.size() - 2] , res[(int)res.size() - 1] , pt[i])) {
res.pop_back();
}
res.push_back(pt[i]);
}
return res;
}
int main() {
int N;
in >> N;
n = N;
pt.resize(n + 1);
for (i = 1; i <= n; i++) {
int X,Y;
in >> X >> Y;
x = X;
y = Y;
pt[i] = {x,y};
}
convexHull();
out << fixed << setprecision(12);
out << res.size() << "\n";
for (auto k : res) {
out << k.x << " " << k.y << "\n";
}
out << "\n";
}