Pagini recente » Cod sursa (job #2375131) | Cod sursa (job #2882386) | Cod sursa (job #54143) | Cod sursa (job #2502290) | Cod sursa (job #3270922)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
const int NMAX = 120002;
using ld = long double;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct puncte {
ld x, y;
}v[NMAX];
ld panta(puncte p0, puncte a, puncte b) { ///comp pantele (0, a), (0, b)
ld nr1 = (a.y - p0.y) * (b.x - p0.x);
ld nr2 = (a.x - p0.x) * (b.y - p0.y);
return nr1 < nr2;
}
bool cmp(puncte a, puncte b) {
return panta(v[1], a, b);
}
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, pos = -1;
puncte p0 = {1000000001, 1000000001}; ///pct cel mai din st
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
if((v[i].x < p0.x) || (v[i].x == p0.x && v[i].y < p0.y)) {
p0 = v[i];
pos = i;
}
}
if(pos > 1)
swap(v[1], v[pos]);
cout << v[1].x << " " << v[1].y << '\n';
sort(v + 2, v + n + 1, cmp);
for(int i = 2; 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) {
//cout << "DECI " << i << '\n';
//cout << s[s.size() - 2].x << " " << s[s.size() - 2].y << '\n';
//cout << s[s.size() - 1].x << " " << s[s.size() - 1].y << '\n';
//cout << v[i].x << " " << v[i].y << '\n';
//cout << determ(s[s.size() - 2], s[s.size() - 1], v[i]) << '\n';
s.pop_back();
}
s.push_back(v[i]);
//cout << "yoo " << i << " " << s.size() << '\n';
}
cout << s.size() << '\n';
for(auto var : s)
cout << setprecision(12) << fixed << var.x << " " << var.y << '\n';
return 0;
}