Pagini recente » Cod sursa (job #2519231) | Cod sursa (job #1155663) | Cod sursa (job #1700085) | Cod sursa (job #2229268) | Cod sursa (job #2987295)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct{
double x;
double y;
};
double eps=1e-12;
punct v[120001];
bool cmp(punct a, punct b){
if(a.x>b.x){
return 0;
}
else if(a.x==b.x){
if(a.y>b.y)
return 0;
else
return 1;
}
else
return 1;
}
double cross(punct O, punct A, punct B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
int st[120001],head;
bool vis[120001];
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);
st[1]=1;
st[2]=2;
head=2;
vis[2]=true;
for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p))) {
if (vis[i]) continue;
while (head >= 2 && cross(v[st[head - 1]], v[st[head]], v[i]) < eps)
vis[st[head--]] = false;
st[++head] = i;
vis[i] = true;
}
cout << head - 1 << "\n";
cout << setprecision(6) << fixed;
for (int i = 1; i < head; ++i)
cout << v[st[i]].x << " " << v[st[i]].y << "\n";
return 0;
}