Pagini recente » Cod sursa (job #372729) | Cod sursa (job #3247950) | Cod sursa (job #509666) | Cod sursa (job #1920753) | Cod sursa (job #1212472)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <stack>
#define DIM 120010
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
pair<double,double> v[DIM],aux;
int S[DIM];
double det(const pair<double,double> &a,const pair<double,double> &b,const pair<double,double> &c){
return (a.first-c.first)*(b.second-c.second)-(b.first-c.first)*(a.second-c.second);
}
int cmp(const pair<double,double> &a,const pair<double,double> &b){
return (det(v[1],a,b)>0);
}
int main(void){
register int i,j,p,q,k;
register double x,y;
f>>n;
p=1;
for(i=1;i<=n;i++){
f>>x>>y,v[i]=make_pair(x,y);
if(v[p]>v[i]) p=i;
}
aux=v[p],v[p]=v[1],v[1]=aux;
sort(v+2,v+n+1,cmp);
S[1]=1,k=2,S[2]=2;
for(i=3;i<=n;i++){
while(k>1 && det(v[S[k]],v[S[k-1]],v[i])>=0)
k--;
S[++k]=i;
}
g<<k<<"\n";
for(i=1;i<=k;i++){
g<<setprecision(9)<<fixed<<v[S[i]].first<<" "<<v[S[i]].second<<"\n";
}
return 0;
}