Pagini recente » Cod sursa (job #1233376) | Cod sursa (job #2795518) | Cod sursa (job #3256129) | Cod sursa (job #3258552) | Cod sursa (job #680814)
Cod sursa(job #680814)
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<vector>
#define lim 120002
using namespace std;
double x[lim],y[lim];
int IndicePunctCurent,IndicePunctPlecare,pozitie,n,i;
bool verif,viz[lim];
double u,maxu,unghi;
vector<int>a;
int main (){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
IndicePunctPlecare=1;
for(i=2;i<=n;i++){
if(x[IndicePunctPlecare]>x[i])
IndicePunctPlecare=i;
}
IndicePunctCurent=IndicePunctPlecare;
u=0;
verif=1;
while(IndicePunctPlecare !=IndicePunctCurent || verif){
verif=0;
a.push_back(IndicePunctCurent);
pozitie=IndicePunctCurent;
maxu=10000;
for(i=1;i<=n;i++){
if(viz[i]||i==IndicePunctCurent) continue;
unghi=atan2((x[i]-x[IndicePunctCurent]),(y[i]-y[IndicePunctCurent]));
if(unghi<0)
unghi+=2*M_PI;
unghi-=u;
if(unghi<0)
unghi+=2*M_PI;
if(maxu>unghi){
maxu=unghi;
pozitie=i;
}
}
u=atan2(-(x[IndicePunctCurent]-x[pozitie]),-(y[IndicePunctCurent]-y[pozitie]));
IndicePunctCurent=pozitie;
if(u<0)
u+=2*M_PI;
viz[IndicePunctCurent]=1;
}
reverse(a.begin(),a.end());
int dim=a.size();
printf("%d\n",dim);
for(i=0;i<dim;i++)
printf("%lf %lf\n",x[a[i]],y[a[i]]);
return 0;
}