Pagini recente » Cod sursa (job #776767) | Cod sursa (job #1091692) | Cod sursa (job #2917420) | Cod sursa (job #12157) | Cod sursa (job #2154455)
#include <cstdio>
#include <algorithm>
using namespace std;
struct punct
{
double x,y;
};
punct v[120010];
vector<punct> q;
double det(punct p1,punct p2,punct p3)
{
return (p1.x-p2.x)*(p1.y-p3.y)-(p1.x-p3.x)*(p1.y-p2.y);
}
int cmp(punct a,punct b)
{
return det(v[1],a,b)>0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
for(int i=2;i<=n;i++)
if(v[i].x<v[1].x) swap(v[i],v[1]);
sort(v+2,v+n+1,cmp);
for(int i=1;i<=n;i++)
{
while(q.size()>1 && det(q[q.size()-2],q.back(),v[i])<0) q.pop_back();
q.push_back(v[i]);
}
printf("%d\n",q.size());
for(int i=0;i<q.size();i++) printf("%.12f %.12f\n",q[i].x,q[i].y);
return 0;
}