Pagini recente » Cod sursa (job #1940831) | Cod sursa (job #1245399) | Cod sursa (job #1253484) | Cod sursa (job #1710485) | Cod sursa (job #1559176)
#include <cstdio>
#include <vector>
#define nmax 120005
#include <math.h>
struct pereche{
double x,y;
};
int N,start;
pereche V[nmax];
vector < int > Rez;
bool viz[nmax];
using namespace std;
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d ",&N);
int i,t,poznoua;
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(t != start){
Rez.push_back(start);
viz[t] = true;
ma = 10000;
poznoua = t;
for(i = 1;i <= N;++i)if(viz[i] == false){
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;
}
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;
}