Pagini recente » Cod sursa (job #2699406) | Cod sursa (job #684168) | Cod sursa (job #1740369) | Cod sursa (job #1980652) | Cod sursa (job #2873094)
// O(N ^ 2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream in("");
ofstream 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);
}
};
int32_t main() {
int n;
in >> n;
vector<point> points(n);
for(int i = 0; i < n; ++i) {
points[i].read();
}
for(int i = 1; i < n; ++i) {
if(points[i].x < points[0].x) {
swap(points[0], points[i]);
}
}
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) {
if(points[currentPoint].orientation(points[j], points[bestPoint]) < 0) {
bestPoint = j;
}
}
}
currentPoint = bestPoint;
}
out << hull.size() << '\n';
for(point it : hull) {
it.write();
}
}