Pagini recente » Cod sursa (job #1032987) | Cod sursa (job #1996282) | Cod sursa (job #3328735) | Cod sursa (job #3311526) | Cod sursa (job #3317211)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int dim = 120002;
struct coord{
double x, y;
int cod;
} v[dim];
int st[dim];
bool cmp(coord A, coord B){
if(A.x != B.x)
return A.x < B.x;
else
return A.y < B.y;
}
double arie(coord a, coord b, coord c){
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;
}
int main()
{
int n, i, k = 1, ck;
in >> n;
for(i = 1; i <= n; ++i)
in >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
coord a = v[1], b = v[n];
for(i = 2; i <= n - 1; ++i)
if(arie(a, b, v[i]) < 0)
v[i].cod = 1;
else
v[i].cod = 2;
st[k] = 1;
for(i = 2; i <= n; ++i)
if(v[i].cod <= 1){
while(k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
--k;
st[++k] = i;
}
ck = k;
st[k] = n;
for(i = n - 1; i; --i)
if(v[i].cod == 2 || v[i].cod == 0){
while(k > ck && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
--k;
st[++k] = i;
}
--k;
out << k << '\n';
for(i = 1; i <= k; ++i)
out << fixed << setprecision(6) << v[st[i]].x << ' ' << v[st[i]].y << '\n';
return 0;
}