Pagini recente » Cod sursa (job #2410209) | Cod sursa (job #3136911) | Cod sursa (job #469160) | Cod sursa (job #900713) | Cod sursa (job #3252711)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct ura{
double x, y;
int parte = 0;
} v[120005];
bool cmp(ura a, ura b){
if(a.x < b.x) return true;
if(a.x > b.x) return false;
if(a.y < b.y) return true;
if(a.y > b.y) return false;
}
double det(ura a, ura b, ura c){
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - c.y * a.x - b.x * a.y;
}
int st[120005];
int main(){
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> v[i].x >> v[i].y;
sort(v+1, v+n+1, cmp);
ura a = v[1], b = v[n];
for(int i = 2; i <= n-1; i++)
if(det(a, b, v[i]) < 0) v[i].parte = 1; /// jos
else v[i].parte = 2; /// deasupra ab
int vf = 1;
st[1] = 1;
for(int i = 2; i <= n; i++){
if(v[i].parte == 1 || v[i].parte == 0){
while(vf > 1 && det(v[st[vf-1]], v[st[vf]], v[i]) < 0)
vf--;
vf++;
st[vf] = i;
}
}
int cvf = vf;
st[vf] = n;
for(int i = n - 1; i >= 1; i--){
if(v[i].parte == 2 || v[i].parte == 0){
while(vf > cvf && det(v[st[vf-1]], v[st[vf]], v[i]) < 0)
vf--;
vf++;
st[vf] = i;
}
}
cout << vf - 1 << '\n';
for(int i = 1; i <= vf - 1; i++)
cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
return 0;
}