Pagini recente » Cod sursa (job #2324166) | Cod sursa (job #3325522) | Cod sursa (job #2002263) | Cod sursa (job #280719) | Cod sursa (job #3336864)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
const int NMAX = 120000;
const int INF = 21e8;
using ll = long double;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct puncte{
ll x, y;
}init[NMAX + 2], p0 = {INF, INF};
ll dist(const puncte& a, const puncte& b) { ///fara radical
return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}
ll determ(const puncte& a, const puncte& b, const puncte& c) { ///NU am impartit la 2
return a.x * b.y + b.x * c.y + c.x * a.y - (a.y * b.x + b.y * c.x + c.y * a.x);
}
bool cmp(const puncte& a, const puncte& b) {
ll panta1 = (a.y - p0.y) * (b.x - p0.x);
ll panta2 = (b.y - p0.y) * (a.x - p0.x);
if(panta1 != panta2)
return panta1 < panta2;
return dist(p0, a) < dist(p0, b);
}
vector <puncte> v; ///stack-ul adica
int main() {
int n, id = 0;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> init[i].x >> init[i].y;
if(init[i].x < p0.x || (init[i].x == p0.x && init[i].y < p0.y)) {
p0 = init[i];
id = i;
}
}
// cout << "ayoo " << p0.x << " " << p0.y << '\n';
/*if(n == 1) {
cout << 0;
return 0;
}
if(n == 2) {
cout << sqrt(dist(init[1], init[2]));
return 0;
}*/
if(id != 1)
swap(init[1], init[id]);
sort(init + 2, init + n + 1, cmp);
/*for(int i = 1; i <= n; i++)
cout << init[i].x << " " << init[i].y << '\n';
cout << '\n';*/
v.push_back(init[1]);
v.push_back(init[2]);
for(int i = 3; i <= n; i++) {
while(v.size() >= 2 && determ(v[v.size() - 2], v.back(), init[i]) < 0)
v.pop_back();
v.push_back(init[i]);
}
cout << v.size() << '\n';
for(auto p : v)
cout << setprecision(12) << fixed << p.x << " " << p.y << '\n';
return 0;
}