Pagini recente » Cod sursa (job #2584228) | Cod sursa (job #2352772) | Cod sursa (job #2319197) | Cod sursa (job #2450917) | Cod sursa (job #900332)
Cod sursa(job #900332)
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
#define MAX 120003
#define PP pair<double,double>
#define x first
#define y second
PP v[MAX];
int S[MAX],n;
double cross_product(PP v1,PP v2,PP v3){
return (v2.x-v1.x)*(v3.y-v1.y)-(v2.y-v1.y)*(v3.x-v1.x);
}
int comp(PP v1,PP v2){
return cross_product(v[1],v1,v2) < 0;
}
int main(){
int i,pymin=1;
PP top;
ifstream f("infasuratoare.in");
f>>n;
for(i=1;i<=n;++i){
f>>v[i].x>>v[i].y;
if(v[i]<v[pymin])
pymin=i;
}
f.close();
swap(v[1],v[pymin]);
sort(v+2,v+n+1,comp);
S[++S[0]]=1;S[++S[0]]=2;
for(i=3;i<=n;++i){
while(cross_product(v[S[S[0]-1]],v[S[S[0]]],v[i])>0 && S[0]>=2)
--S[0];
S[++S[0]]=i;
}
ofstream g("infasuratoare.out");
g<<fixed<<S[0]<<"\n";
for(i=S[0];i;--i)
g<<setprecision(6)<<v[S[i]].x<<" "<<v[S[i]].y<<"\n";
g.close();
return 0;
}