Pagini recente » Cod sursa (job #1824933) | Cod sursa (job #2564676) | Cod sursa (job #2826171) | Cod sursa (job #213086) | Cod sursa (job #2710132)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define per pair<double,double>
#define x first
#define y second
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int nmx = 12e4 + 5;
int n, top;
per v[nmx], st[nmx];
void read(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> v[i].x >> v[i].y;
}
void minim(){
int mn = 1;
for(int i = 2; i <= n; i++)
if(v[i] < v[mn])
mn = i;
swap(v[1], v[mn]);
}
double cross_prod(per a, per b, per c){
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(per a, per b){
return cross_prod(v[1], a, b) < 0;
}
void solve(){
st[1] = v[1];
st[2] = v[2];
top = 2;
for(int i = 3; i <= n; i++){
while(top >= 2 && cross_prod(st[top - 1], st[top], v[i]) > 0)
--top;
st[++top] = v[i];
}
}
void print(){
cout << top << "\n";
for(int i = top; i >= 1; i--)
cout << fixed << setprecision(9) << st[i].x << " " << st[i].y << "\n";
}
int main()
{
read();
minim();
sort(v + 2, v + n + 1, cmp);
solve();
print();
return 0;
}