Pagini recente » Cod sursa (job #890621) | Cod sursa (job #289764) | Cod sursa (job #727778) | Cod sursa (job #3340148) | Cod sursa (job #3317166)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
int st[120001];
struct ura {
double x, y;
int ok;
};
ura v[120001];
bool cmp(ura a, ura b) {
if(a.x < b.x)
return true;
if(a.x == b.x && a.y < b.y)
return true;
return false;
}
double arie(ura a, ura b, ura c) {
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
int main()
{
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
int n, i, k, kc;
cin >> n;
for(i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmp);
for(i = 2; i < n; i++) {
if(arie(v[1], v[n], v[i]) < 0)
v[i].ok = 1;
else
v[i].ok = 2;
}
k = 1;
st[1] = 1;
for(i = 2; i <= n; i++) {
if(v[i].ok < 2) {
for(; k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0; k--) {
}
k++;
st[k] = i;
}
}
kc = k;
for(i = n - 1; i >= 1; i--) {
if(v[i].ok == 2 || v[i].ok == 0) {
for(; k > kc && arie(v[st[k - 1]], v[st[k]], v[i]) < 0; k--) {
}
k++;
st[k] = i;
}
}
k--;
cout << k << '\n';
for(i = 1; i <= k; i++)
cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
return 0;
}