Pagini recente » Cod sursa (job #1670765) | Cod sursa (job #1556577) | Cod sursa (job #3190493) | Cod sursa (job #811180) | Cod sursa (job #1110358)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct {
double x;
double y;
}v[120010];
int i, p,s[120010],n,imin;
double minim,aux1,aux2;
int arie (punct i, punct j, punct k) {
double ariec = (j.x-i.x)*(k.y-i.y)-(k.x-i.x)*(j.y-i.y);
if (ariec<0.000000000001)
return 1;
else
return 0;
}
int cmp (punct a, punct b) {
return arie(v[1],a,b);
}
int main () {
fin>>n;
minim=1000000000;
for (i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
if (v[i].x<minim) {
minim=v[i].x;
imin=i;
}else
if (v[i].y<v[imin].y)
imin=i;
}
aux1=v[1].x;aux2=v[1].y;
v[1].x=v[imin].x;v[1].y=v[imin].y;
v[imin].x=aux1;v[imin].y=aux2;
sort (v+2,v+n+1,cmp);
s[1]=n;
s[2]=n-1;
p=2;
for (i=n-2;i>=1;i--) {
while( arie (v[s[p-1]],v[s[p]],v[i]) && p>=1 )
p--;
s[++p]=i;
}
fout<<p<<"\n";
fout << setprecision(6) << fixed;
for (i=1;i<=p;i++)
fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
return 0;
}