Pagini recente » Cod sursa (job #2886855) | Cod sursa (job #3141158) | Cod sursa (job #2936011) | Cod sursa (job #3264994) | Cod sursa (job #2988407)
#include<bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,d[10001],a[100001];
float s;
struct pct{
double x, y;
}v[120100],st[120100];
double det(pct a, pct b, pct c) {
return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
int comp(pct a, pct b) {
return a.y<b.y;
}
int comp1(pct a, pct b) {
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int comp2(pct b, pct c) {
return det(v[1],b,c)<0;
}
int main()
{in>>n;
for(int i=1;i<=n;i++)
in>>v[i].x>>v[i].y;
sort(v+1,v+n+1,comp1);
st[1]=v[1];
sort(v+2,v+n+1,comp2);
st[2]=v[2];
int k=2;
for(int i=3;i<=n;i++)
{while(k>2 && det(st[k-1],st[k],v[i])>0)
k--;
st[++k]=v[i];
}
out<<k<<'\n';
for(int i=k;i>=1;i--)
out<<fixed<<setprecision(6)<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}