Pagini recente » Cod sursa (job #3250453) | Cod sursa (job #154646) | Cod sursa (job #700506) | Cod sursa (job #2961730) | Cod sursa (job #3317155)
#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;
}
st[1] = 1;
k = 1;
for(i = 2; i < n; i++) {
if(v[i].ok == 1) {
for(; k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0; k--) {
}
k++;
st[k] = i;
}
}
k++;
st[k] = n;
kc = k;
for(i = n - 1; i > 1; i--) {
if(v[i].ok == 2) {
for(; k > kc && arie(v[st[k - 1]], v[st[k]], v[i]) < 0; k--) {
}
k++;
st[k] = i;
}
}
cout << k << '\n';
for(i = 1; i <= k; i++) {
cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
}
return 0;
}