Pagini recente » Cod sursa (job #1950634) | Cod sursa (job #940867) | Cod sursa (job #834939) | Cod sursa (job #2269193) | Cod sursa (job #1559188)
#include <cstdio>
#include <vector>
#define nmax 120005
#include <math.h>
using namespace std;
struct pereche{
double x,y;
};
int N,start;
pereche V[nmax];
vector <int> Rez;
bool viz[nmax];
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d ",&N);
int i,t,poznoua;
bool m = true;
double x,y,unghi,lst = 0,ma;
for(i = 1;i <= N;++i){
scanf("%lf %lf ",&V[i].x,&V[i].y);
if(i == 1 || V[start].x > V[i].x || (V[start].x == V[i].x && V[start].y > V[i].y))
start = i;
}
t = start;
while(m == true || t != start){ ///folosim variabila m pentru a intra in bucla
Rez.push_back(t);
ma = 10000;
m = false;
poznoua = t;
for(i = 1;i <= N;++i){
if(viz[i] == true || t == i)continue;
unghi = atan2(V[i].x - V[t].x,V[i].y - V[t].y);
if(unghi < 0)unghi += 2*M_PI;
unghi -= lst; ///scadem unghiul cu care s-a intors varful curent fata de varful precedent
if(unghi < 0)unghi += 2*M_PI;
if(ma > unghi){ ///actualizam unghiul maxim gasit(ma) si varful pentru care a fost gasita aceasta valoare
ma = unghi;
poznoua = i;
}
}
lst = atan2(V[poznoua].x - V[t].x,V[poznoua].y - V[t].y); ///calculam noul unghi (relativ)
if(lst < 0)lst += 2*M_PI;
t = poznoua;
viz[t] = true;
}
printf("%d\n",Rez.size());
for(i = Rez.size() - 1;i >= 0;i--)printf("%lf %lf\n",V[Rez[i]].x,V[Rez[i]].y);
printf("\n");
return 0;
}