Pagini recente » Borderou de evaluare (job #1511119) | Cod sursa (job #790077) | Borderou de evaluare (job #1513806) | Cod sursa (job #1576821) | Cod sursa (job #3310399)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <iomanip>
using namespace std;
const int NMAX = 120000; ///120000 pt infasuratoare
using ld = long double;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
double p0x, p0y;
struct puncte{
double x, y;
double unghi;
bool operator <(const puncte& rhs) const {
if(unghi != rhs.unghi)
return unghi < rhs.unghi;
double dista = (p0x - x) * (p0x - x) + (p0y - y) * (p0y - y);
double distb = (p0x - rhs.x) * (p0x - rhs.x) + (p0y - rhs.y) * (p0y - rhs.y);
return dista < distb;
}
}v[NMAX + 2];
set <puncte> s;
double determ(const puncte& a, const puncte& b, const puncte& c) {
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;
}
vector <puncte> st;
int main() {
int n, m;
cin >> n;
p0x = 0, p0y = 0;
for(int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
p0x += v[i].x, p0y += v[i].y;
}
p0x /= n, p0y /= n;
for(int i = 1; i <= n; i++)
v[i].unghi = atan2(v[i].y - p0y, v[i].x - p0x);
sort(v + 1, v + n + 1);
st.push_back(v[1]);
st.push_back(v[2]);
for(int i = 3; i <= n; i++) {
while(st.size() >= 2 && determ(st[st.size() - 2], st[st.size() - 1], v[i]) < 0)
st.pop_back();
st.push_back(v[i]);
}
int sizee = st.size(), ult = 0; /// o sa se tot schimbe size-ul
while(sizee > 3) { ///ne intereseaza doar cum se termina CAPETELE
if(determ(st[st.size() - 2], st[st.size() - 1], st[ult]) < 0) {
st.pop_back();
sizee--;
}
else if(determ(st[st.size() - 1], st[ult], st[ult + 1]) < 0) {
ult++;
sizee--;
}
else
break;
}
cout << sizee << '\n';
for(int i = ult; i < st.size(); i++)
cout << setprecision(12) << fixed << st[i].x << " " << st[i].y << '\n';
return 0;
}