Pagini recente » Cod sursa (job #646466) | Cod sursa (job #2524688) | Cod sursa (job #1770301) | Cod sursa (job #1227707) | Cod sursa (job #1822839)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct Point{
double x, y;
Point(pair<double, double> pa): x(pa.first), y(pa.second) {}
};
double prod (Point a, Point b, Point c) {
return (c.y - a.y)*(b.x - a.x) - (c.x - a.x)*(b.y - a.y);
}
int main() {
const double eps = 1e-12;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin>>n;
vector <pair <double, double>> v(n);
vector <int> sol(n), vis(n, 0);
for (auto &p: v) {
fin>>p.first>>p.second;
}
//vis[0] = 1; we want to meet this point again, so we don't mark visited
sort(v.begin(), v.end());
sol[0] = 0;
sol[1] = 1;
int m = 2;
vis[0] = vis[1] = 1;
for (int i = 2; i < n; i++) {
Point nou = Point(v[i]);
while (m > 1 && prod(Point(v[sol[m-2]]), Point(v[sol[m-1]]), nou) < eps)
vis[sol[--m]] = 0;
sol[m] = i;
vis[sol[m++]] = 1;
}
for (int i = n-1; i > 0; i--) {
Point nou = Point(v[i]);
if (vis[i])
continue;
while (m > 1 && prod(Point(v[sol[m-2]]), Point(v[sol[m-1]]), nou) < eps)
m--;
sol[m++] = i;
}
for (int i = 0; i < m; i++)
cout<<v[sol[i]].first<<" "<<v[sol[i]].second<<endl;
return 0;
}