Pagini recente » Cod sursa (job #3276362) | Cod sursa (job #3188355) | Cod sursa (job #1913915) | Cod sursa (job #1534623) | Cod sursa (job #3273241)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
const int NMAX = 120002;
using ld = long double;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct puncte {
ld x, y;
ld unghi;
}v[NMAX], p0;
bool cmp(puncte a, puncte b) {
return a.unghi < b.unghi;
}
ld determ(puncte a, puncte b, puncte c) { ///aria triun
return a.x * b.y + b.x * c.y + c.x * a.y -
b.y * c.x - c.y * a.x - a.y * b.x;
}
vector <puncte> s;
int main()
{
int n;
p0 = {0, 0}; ///media aritm
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
p0.x += v[i].x;
p0.y += v[i].y;
}
p0.x /= n;
p0.y /= n;
for(int i = 1; i <= n; i++) {
v[i].unghi = atan2(v[i].y - p0.y, v[i].x - p0.x);
}
//cout << p0.x << " " << p0.y << '\n';
sort(v + 1, v + n + 1, cmp);
/*for(int i = 1; i <= n; i++)
cout << v[i].x << " " << v[i].y << '\n';
cout << '\n';*/
s.push_back(v[1]);
s.push_back(v[2]);
for(int i = 3; i <= n; i++) {
while(s.size() >= 2 && determ(s[s.size() - 2], s[s.size() - 1], v[i]) < 0) {
s.pop_back();
}
s.push_back(v[i]);
//cout << "yoo " << i << " " << s.size() << '\n';
}
int sizee = s.size();
int ult = 0; ///ult nr valid din st
while(sizee > 3) {
if(determ(s[s.size() - 2], s[s.size() - 1], s[ult]) < 0) {
s.pop_back();
sizee--;
}
else if(determ(s[s.size() - 1], s[ult], s[ult + 1]) < 0) {
ult++;
sizee--;
}
else
break;
}
/*while(sizee > 3 & determ(s[s.size() - 2], s[s.size() - 1], s[ult]) < 0) {
ult++;
sizee--;
}*/
cout << sizee << '\n';
for(int i = ult; i < s.size(); i++)
cout << setprecision(12) << fixed << s[i].x << " " << s[i].y << '\n';
return 0;
}