Pagini recente » Cod sursa (job #491715) | Cod sursa (job #1253727) | Cod sursa (job #478392) | Cod sursa (job #3231685) | Cod sursa (job #2873099)
// O(N ^ 2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point {
long double x, y;
void read() {
in >> x >> y;
}
void write() {
out << fixed << setprecision(12) << x << ' ' << y << '\n';
}
point operator - (const point &B) const {
return point{x - B.x, y - B.y};
}
void operator -= (const point &B) {
x -= B.x;
y -= B.y;
}
int operator * (const point &B) const {
return x * B.y - y * B.x;
}
int orientation(const point &A, const point &B) const {
return (A - *this) * (B - *this);
}
bool operator <(const point &A) {
if(x == A.x) {
return y < A.y;
}
return x < A.x;
}
};
int32_t main() {
int n;
in >> n;
vector<point> points(n);
for(int i = 0; i < n; ++i) {
points[i].read();
}
sort(points.begin(), points.end());
vector<point> hull;
vector<bool> marked(n, false);
int currentPoint = 0;
while(!marked[currentPoint]) {
marked[currentPoint] = true;
hull.push_back(points[currentPoint]);
int bestPoint = 0;
if(!currentPoint) bestPoint = 1;
for(int j = 0; j < n; ++j) {
if(j != currentPoint && j != bestPoint && !marked[j]) {
if(points[currentPoint].orientation(points[j], points[bestPoint]) < 0) {
bestPoint = j;
}
}
}
currentPoint = bestPoint;
}
out << hull.size() << '\n';
for(point it : hull) {
it.write();
}
}