Pagini recente » Cod sursa (job #412536) | Cod sursa (job #1253849) | Cod sursa (job #155467) | Cod sursa (job #2053127) | Cod sursa (job #2417201)
#include <bits/stdc++.h>
#define DIM 120005
#define x first
#define y second
using namespace std;
int st1[DIM],st2[DIM];
pair<double,double> v[DIM];
double cross_product(int p0,int p1,int p2) {
return (v[p1].x-v[p0].x)*(v[p2].y-v[p0].y)-(v[p2].x-v[p0].x)*(v[p1].y-v[p0].y);
}
int main()
{ int n,i;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for (i=1;i<=n;++i)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1);
int nr1=2;st1[1]=1,st1[2]=2;
for (i=3;i<=n;++i) {
while (nr1>=2 && cross_product(st1[nr1-1],st1[nr1],i)<0)
--nr1;
++nr1,st1[nr1]=i;
}
int nr2=2;st2[1]=n,st2[2]=n-1;
for (i=n-2;i>=1;--i) {
while (nr2>=2 && cross_product(st2[nr2-1],st2[nr2],i)<0)
--nr2;
++nr2,st2[nr2]=i;
}
g<<nr1+nr2-2<<'\n';
for (i=1;i<=nr1;++i)
g<<fixed<<setprecision(12)<<v[st1[i]].x<<" "<<v[st1[i]].y<<'\n';
for (i=2;i<nr2;++i)
g<<fixed<<setprecision(12)<<v[st2[i]].x<<" "<<v[st2[i]].y<<'\n';
return 0;
}